遍历马尔可夫链问题：证明修正转移概率矩阵的遍历性

好的，我来帮你理清$\tilde{P}$不可约性的证明思路——其实核心是利用原链$P$的不可约性，结合$\tilde{P}$的构造逻辑来推导：

首先回顾不可约马尔可夫链的核心定义：对于任意两个状态$i,j$（包括$i=j$的情况），存在正整数$n$，使得从$i$出发经过$n$步到达$j$的概率$\tilde{P}^n(i,j) > 0$。

我们分两种情况讨论：

1. 当$i = j$时 #

直接看$\tilde{P}$的对角元：$\tilde{P}(i,i) = pP(i,i) + (1-p)$。因为$0 < p < 1$，所以$1-p > 0$，不管原链$P$的对角元$P(i,i)$是什么，$\tilde{P}(i,i)$必然大于0。这说明从$i$到自身一步就能到达，完全满足不可约性的要求。

2. 当$i \neq j$时 #

因为原链$P$是不可约的，根据定义，必然存在某个正整数$m$，使得$P^m(i,j) > 0$（也就是原链中从$i$出发，经过$m$步能以正概率走到$j$）。

现在看$\tilde{P}^{m(i,j)$，我们可以用二项式定理展开$\tilde{P}}m = (pP + (1-p)I)^m$，得到：
$$\tilde{P}^m = \sum_{k=0}^m \binom{m}{k} p^k (1-p)^{m-k} P^k$$
对应到元素$\tilde{P}^m(i,j)$就是：
$$\tilde{P}^m(i,j) = \sum_{k=0}^m \binom{m}{k} p^k (1-p)^{m-k} P^k(i,j)$$

这里面当$k = m$时，对应的项是$\binom{m}{m} p^m (1-p)^0 P^m(i,j) = p^m P^m(i,j)$。因为$0 < p < 1$，所以$p^m > 0$，再加上$P^m(i,j) > 0$，这一项的结果肯定是正的。而求和里的其他项都是非负的（概率本身是非负的），所以整个$\tilde{P}^m(i,j)$必然大于0。

换个更直观的说法：在$\tilde{P}$对应的链中，我们可以选择连续$m$步都严格按照原链$P$的规则转移（每步选$P$转移的概率是$p$），完全不触发原地停留的操作。这条路径的概率就是$p^m \times P^m(i,j)$，显然大于0，直接证明了从$i$到$j$经过$m$步可达。

结合两种情况，任意两个状态之间都存在可达的路径，所以$\tilde{P}$对应的马尔可夫链是不可约的。再加上你已经证明的非周期性，就可以得出$\tilde{P}$具有遍历性的结论了。

内容的提问来源于stack exchange，提问作者Betelgeuse