在有限状态马尔可夫链的前n步中至少访问状态k一次的概率

Question

假设 $M$ 状态的马尔可夫链，并假设从状态 $X_0$ 开始，我想知道是否有一种方法可以计算在前 n 个步骤中至少访问一次状态 $X_k$ 的概率。 任何帮助将不胜感激！

我不认为有一个封闭形式的表达，但我希望我是错的。到目前为止，我正在尝试使用模拟来估计它。

Answer 1

这些概率可以使用以下算法进行估计：

1. 初始化计数器 = 0

2. 对于 N 次迭代（N 个较大）：

   • 通过 n 个步骤模拟马尔可夫链
   • 如果访问了状态 k，则计数器加 1

3. 通过 counter / N 估计所需概率（即访问状态 k 的模拟实现的比例）

我在下面添加了 R 代码来执行此操作，适用于具有我选择的转移概率矩阵的 5 状态马尔可夫链。在代码中，我跟踪所有状态的“计数器”。

# Number of states
M <- 5

# Transition probability matrix
tpm <- matrix(c(0.5, 0.1, 0.1,   0,   0,
                0  ,   0, 0.5, 0.2, 0.3,
                0  , 0.1, 0.9,   0,   0,
                0.1, 0.2,   0, 0.3, 0.5,
                0  ,   0,   0, 0.2, 0.8),
              nrow = M, byrow = TRUE)

# Length of realisation
n <- 10
# Initial state
X0 <- 2

# Iterate over many simulations
n_rep <- 1e4
counts <- rep(0, M)
for(rep in 1:n_rep) {
    # Simulate Markov chain
    X <- rep(X0, n)
    for(i in 2:n) {
        X[i] <- sample(1:M, size = 1, prob = tpm[X[i-1],])
    }
    # Check which states have been visited
    visited_states <- unique(X)
    counts[visited_states] <- counts[visited_states] + 1
}

# Proportion of simulations where each state was visited
prop <- counts / n_rep

在这个例子中，我们发现：

> prop
[1] 0.0880 1.0000 0.6064 0.5470 0.5817

也就是说，如果我们从状态 2（变量

X0

）开始并运行链 10 步（变量

n

），访问状态 1 的概率约为 0.088。正如预期的那样，访问状态 2 的概率为 1，因为那是我们开始的地方。