证明Markov 链的逆序也构成一个 Markov 链

设原始的 Markov 链为 $(X_n)_{n\geq 0}$，其状态空间为 $\mathcal{S}$，转移概率矩阵为 $P$。定义逆序的 Markov 链为 $(Y_n)_{n\geq 0}$，其状态空间为 $\mathcal{S}$，转移概率矩阵为 $Q$，其中 $Q_{ij} = \mathbb{P}(Y_{n-1} = i | Y_n = j)$。 我们需要证明 $Q$ 满足马尔可夫性质，即对于任意 $n\geq 0$ 和 $i_0, i_1, \ldots, i_n \in \mathcal{S}$，有 $$ \mathbb{P}(Y_n = i_n | Y_{n-1} = i_{n-1}, \ldots, Y_0 = i_0) = \mathbb{P}(Y_n = i_n | Y_{n-1} = i_{n-1}) $$ 根据条件概率的定义，左边可以写成 $$ \begin{aligned} &\mathbb{P}(Y_n = i_n | Y_{n-1} = i_{n-1}, \ldots, Y_0 = i_0) \\ =& \frac{\mathbb{P}(Y_n = i_n, Y_{n-1} = i_{n-1}, \ldots, Y_0 = i_0)}{\mathbb{P}(Y_{n-1} = i_{n-1}, \ldots, Y_0 = i_0)} \\ =& \frac{\mathbb{P}(X_0 = i_n, X_1 = i_{n-1}, \ldots, X_n = i_0)}{\mathbb{P}(X_0 = i_{n-1}, X_1 = i_{n-2}, \ldots, X_{n-1} = i_0)} \\ =& \frac{P_{i_{n-1}, i_n} P_{i_{n-2}, i_{n-1}} \cdots P_{i_0, i_1}}{P_{i_{n-2}, i_{n-1}} P_{i_{n-3}, i_{n-2}} \cdots P_{i_0, i_1}} \\ =& Q_{i_n, i_{n-1}} \\ =& \mathbb{P}(Y_n = i_n | Y_{n-1} = i_{n-1}) \end{aligned} $$ 其中第二步到第三步使用了逆序 Markov 链的定义，第四步到第五步使用了转移概率矩阵的定义。因此，逆序的 Markov 链也满足马尔可夫性质，即也是一个 Markov 链。