马尔可夫链可达性证明问询：M步内可达与零转移概率推导

这两个结论是马尔可夫链基础理论里的关键内容，咱们一步步拆解来推导：

结论1：若状态j可从状态i到达，则j可在M步或更少步数内到达 #

咱们用反证法来梳理逻辑：
假设从i到j的最短路径长度为$k > M$，这条路径对应的状态序列是：
$$i = s_0, s_1, s_2, ..., s_k = j$$
这个序列里一共有$k+1$个状态，但整个马尔可夫链只有$M$个不同状态。根据鸽巢原理，这$k+1$个状态里必然存在重复的状态——比如存在$0 ≤ t < s ≤ k$，使得$s_t = s_s$。

这时候，从$s_t$到$s_s$的这段是一个循环，咱们可以直接把这段循环“剪掉”，得到一条更短的路径：
$$i = s_0, ..., s_t, s_{s+1}, ..., s_k = j$$
这条新路径的长度是$k - (s - t)$，比原来的$k$要短。咱们可以重复这个“剪循环”的操作，直到路径长度≤M为止。

这就说明，必然存在一条长度不超过M的路径从i到j，也就是j可在M步或更少步数内到达。

结论2：若对所有$n ≤ M$，有$P_{ij}^n = 0$，则对所有自然数$n$，$P_{ij}^n = 0$ #

同样用反证法来推导：
假设存在某个自然数$n > M$，使得$P_{ij}^n > 0$。这意味着存在至少一条长度为$n$的路径从i到j。

根据结论1的结论，既然i能到达j，那必然存在一条长度≤M的路径从i到j——也就是说，存在某个$k ≤ M$，使得$P_{ij}^k > 0$。但这和前提“所有$n ≤ M$时$P_{ij}^n = 0$”直接矛盾。

所以这个假设不成立，也就是说，对所有自然数$n$，$P_{ij}^n = 0$。

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