如何证明马尔科夫链一定会达到稳态？ 第1页

这个不一定。马尔科夫链未必有稳态。我们知道，马尔科夫链可以用这个递归方程表示：

其中 表示时刻 的状态向量， 表示马尔科夫链的状态转移矩阵。如果马尔科夫链有稳态解，则对上面的转移方程两边求极限得到

也就是如果马尔科夫链有稳态解，则这个稳态一定是转移矩阵的特征值为1的右特征向量。所以如果状态转移矩阵有唯一的一个特征值为1的右特征向量，则马尔科夫链就有稳态解，否则没有。那么问题是什么时候状态转移矩阵有唯一的特征值为1的右特征向量？这个要用到Perron-Frobenius定理。该定理为：

这个定理的描述和证明都挺费时间的。对于马尔科夫链的转移矩阵而言，显然它满足矩阵元素都是非负这个条件，除此之外它还需要是一个不可约矩阵。这时，转移矩阵的谱半径就是它最大的特征值，为1，而且该特征值的代数重数为1，但是这个条件还不能保证马尔科夫链的稳态解一定存在，因为尽管特征值1的代数重数为1，但是该矩阵仍然有可能有特征值为 ，也就是该矩阵的spectral circle上有可能还有别的复根。为了排除这种情况，我们还需要求转移矩阵为primitive matrix，也就是

所以如果进而要求转移矩阵是primitive matrix，则可以保证矩阵的spectral circle上只有一个根，且该特征根为 的最大特征值，为1. 此时马尔科夫链有唯一的稳态解。

矩阵 是primitive matrix的一个充分但非必要条件是 至少有一个对角元素大于零。除此之外，还有一个方法可以判断一个非负矩阵是否为primitive，

这个方法给出判断primitivity的充要条件，但是真正要用这个判据的时候需要计算矩阵的高次幂。这个定理等价于， 如果一个马尔科夫链的转移矩阵是primitive matrix，那么从任意状态出发，经过足够长的时间，这个马尔科夫链一定可以访问到每一个状态。此时称马尔科夫链为ergodic. 至于如何快速判断一个转移矩阵是否是primitive matrix，这个我还真不知道。

如果一个矩阵是primitive matrix，那么我们可以用power iteration method求解它的最大特征向量。这个算法也是PageRank算法的基础。PageRank算法里面引入了一个跳跃因子 其实就是为了保证对于任意的图，它的概率转移矩阵总是一个primitive matrix，从而可以用power iteration来计算它的最大特征向量。这个最大特征向量又叫做Perron vector.