马尔科夫过程与动态规划密切相关。

对于有限马尔科夫过程(马尔科夫链)，很容易使用概率转移图或概率转移矩阵P表示。

\[\boldsymbol\pi_{i+1} P=\boldsymbol\pi_i\]

因为转移的无后效性，n步的转移概率矩阵即P^n，从而可通过矩阵来研究Markov chain的性质。

可达性和可约性、周期性

若存在n>0，\(P^{(n)}_{ij}>0\)，则j为从状态i可达。若ij互相可达，则互通。所有互通的状态构成一个类。显然在转移图上，互通构成强联通分量。

若存在两个状态不互通，则马氏链可约，否则不可约。有可约性时，可以考虑拆开处理。此时矩阵为准三角矩阵。

若对于n>0，有\( P^{(n)}_{ii}>0\)，即可以从i返回到自身，则称对应指标的gcd称为i的周期d。若d=1，则称i是非周期的。若集合为空，也称i的周期为无穷大。

按照定义，可能前几个周期并不能返回，例如满足条件的n为6,8,10,…。

显然同一个类中状态的周期是相同的。

常返性

设\( f^{(n)}_{ij} = P\{X_n=j, X_k\neq j, 0<k<n |X_0=i\}\)，即在第n步首次从i达到j的概率。

令\( f_{ij}=\sum_{n=1}^{\infty}{f^{(n)}_{ij}}\)， 若\(f_{jj}=1\)，称j为常返态，否则为非常返态。非常返性说明从i出发不一定能回到自身。

又设\( \mu_{i}=\sum_{n=1}^{\infty}{nf^{(n)}_{ii}}\)，即返回所需步数的期望。对常返状态i，\(\mu_{ii}<+\infty\)时称为正常返状态，否则为零常返状态。同一类的状态具有相同的常返性，它们同时为正/非/零常返态之一。

若状态i非周期而且正常返，称i是遍历的。若i遍历且i到自身概率为1，称i为吸收状态。

常返性的一个充要条件：若$$\sum_{n=1}^{\infty}{f^{(n)}_{ij}}=\infty$$ 则状态常返，否则$$\sum_{n=1}^{\infty}{f^{(n)}_{ij}}=\frac{1}{1-f_{ii}}$$

平稳性

大部分情况下，多次转移后概率分布迅速收敛于平稳分布。该分布与矩阵的性质有关，而与初始状态无关。

极限定理

极限定理即为平稳分布。

若i是周期d的常返态，则$$\mathop{\lim}_{n\to\infty} p^{nd}_{ij}=\frac{d}{\mu_i}$$显然i不为正常返状态时极限分布为0。

推论：有限状态的马氏链没有零常返态，不可约有限链都是正常返的。无限状态时，若有零常返态，则有无穷多个。

遍历链的极限分布

若每一个状态都遍历，则马尔科夫链为遍历链。对可约的遍历链，此时有\[\mathop{\lim}_{n\to\infty} p^{n}_{ij}=\pi_i=\frac{1}{\mu_i}\]

若非周期马氏链不可约，它仍有唯一的稳定分布\(\mathop{\lim}_{n\to\infty} p^{n}_{ij}=\pi_i\)。除非所有的状态均非正常返使得稳定分布不存在。

遍历性的本质即n趋于无穷时，P的n次幂存在不依赖于i的极限，就是平稳分布π。

极限分布的计算

对遍历链，只要解线性方程组 \(\pi P=\pi, \sum{\pi}=1 \)即可。

吸收链的处理

特征分解

稳定分布π为矩阵P的特征向量，而且特征值为1。

如果P稳定且存在特征分解，那么可见其特征值均不大于1，极限分布也可用特征分解求得。

对于周期状态，特征分解一般为复数，其幅角为周期d次的单位根。