3.3　矩阵的极限与马尔科夫链

先来看一个例子。社会学家经常把人按其经济状况分成3类：下层（lower-class）、中层（middle-class）、上层（upper-class），用1、2、3分别代表这三个阶层。社会学家们发现决定一个人的收入阶层的最重要的因素就是其父母的收入阶层。如果一个人的收入属于下层类别，那么他的孩子属于下层收入的概率是0.65，属于中层收入的概率是0.28，属于上层收入的概率是0.07。从父代到子代，收入阶层的变化的转移概率如图3-15所示。

使用矩阵的表示方式，转移概率矩阵记为

假设当前这一代人处在下、中、上层的人的比例是概率分布向量π₀=［π₀（1），π₀（2），π₀（3）］，那么他们的子女的分布比例将是π₁=π₀P，孙子代的分布比例将是π₂=π₁P=π₁P²=…，第n代子孙的收入分布比例将是π_n=π_n-1P=…=π₀Pⁿ。假设初始概率分布为π₀=［0.21，0.68，0.11］，则可以计算前n代人的分布状况如下：

发现从第7代人开始，这个分布就稳定不变了，这个是偶然的吗？我们换一个初始概率分布π₀=［0.75，0.15，0.1］试试看，继续计算前n代人的分布状况如下

结果，到第9代人的时候，分布又收敛了。最为奇特的是，两次给定不同的初始概率分布，最终都收敛到概率分布π=［0.286，0.489，0.225］，也就是说收敛的行为和初始概率分布π₀无关。这说明这个收敛行为主要是由概率转移矩阵P决定的。计算一下Pⁿ，

我们发现，当n足够大的时候，这个Pⁿ矩阵的每一行都是稳定地收敛到π=［0.286，0.489，0.225］这个概率分布。自然地，这个收敛现象并非是这个例子所独有，而是绝大多数“马尔科夫链”的共同行为。

为了求得一个理论上的结果，再来看一个更小规模的例子（这将方便后续的计算演示），假设在一个区域内，人们要么是住在城市，要么是住在乡村。下面的矩阵表示人口迁移的一些规律（或倾向）。例如，第1行第1列就表示，当前住在城市的人口，明年将会有90%的人选择继续住在城市。

作为一个简单的开始，来计算一下现今住在城市的人中2年后会住在乡村的概率有多大。分析可知，当前住在城市的人，1年后，会有90%继续选择住在城市，另外10%的人则会选择搬去乡村居住。然后又过了1年，上一年中选择留在城市的人中又会有10%的人搬去乡村。而上一年中搬到乡村的人中将会有98%的选择留在乡村。这个分析过程如图3-16所示，最终可以算出现今住在城市的人中2年后会住在乡村的概率=0.90×0.10+0.10×0.98。

其实上述计算过程就是在做矩阵的平方。在下面给出的矩阵乘法中，你会发现结果矩阵中第2行第1列的计算就是在执行上面的操作。在此基础，我们还可以继续计算n年后的情况，也就是计算矩阵A自乘n次后的结果。

如果假设最开始的时候，城乡人口的比例为7:3，可以用一个列向量来表示它，即P=［0.7，0.3］^T，想知道最终城乡人口的比例为何，则就是要计算。如果最初城乡人口的比例为9:1，结果又如何呢？这些都要借助矩阵的极限，对角化操作以及马尔科夫链等概念来辅助计算。

来辨析三个概念：随机过程、马尔科夫过程、马尔科夫链。这三个概念中，都涉及对象和它们对应的状态这两个要素。在刚刚给出的例子中，研究的对象就是人，人的状态分为住在城市或者住在乡村两种。

三者之中，最宽泛的概念就是随机过程，限制最多的就是马尔科夫链。对于马尔科夫链，必须满足两个条件：①当前状态仅跟上一个状态有关；②总共的状态数是有限的。如果状态数可以是无限多个，那样的问题就称为马尔科夫过程。但在马尔科夫过程中仍然要求，时间是离散的，例如前面的例子是以“年”为单位的。如果时间允许是连续的，那样的问题就称为随机过程。本书仅仅讨论马尔科夫链。

在某个时间点上，对象的状态为s₁，下一个时刻，它的状态以某种概率转换到其他状态（也包含原状态s₁），这里所说的“以某种概率转换”最终是通过状态转移矩阵（或称随机矩阵）的形式来给出的。转移矩阵的定义如下：

令，假设：

（1）A_ij≥0；

（2）对于所有的1≤j≤n，。

那么，A称为一个转移矩阵（或随机矩阵）。矩阵A的列向量被称为概率向量。

此外，如果矩阵的某个次幂仅包含正数项，该转移矩阵称为是正则的。这里，“某个”的意思就是存在一个整数n使得对于所有的i，j，有（Aⁿ）_ij＞0。

从状态转移矩阵中，（结合之前的例子）可以看出A_ij元素给出的信息就是（在一个单位时间间隔内）对象从状态j转移到状态i的概率。令P=（p₀，p₁，…，p_n）^T是一个向量，如果对于所有的i，有p_i≥0以及∑p_i=1，那么P就称为一个概率向量（probability vector）。所以可以看出，任意一个转移矩阵中的某一列都是一个概率向量。

定理：令A是一个n×n的正则转移矩阵。那么：

（1）1一定是矩阵A的一个特征值，并且1的几何重数等于1，除此之外，所有其他的特征值之绝对值都小于1；

（2）A可以对角化，并且存在；

（3）是一个转移矩阵；

（4）AL=LA=L；

（5）矩阵L=［v，v，…，v］，即L的每一列都一样，都是v。而且v就是矩阵A相对于特征值1的特征向量；

（6）对于任意概率向量w，都有。

这个定理非常非常奇妙的地方就是它解答了之前那个令人困扰的问题！原问题是：如果假设最开始的时候，城乡人口的比例为7:3，可以用一个列向量来表示它P=［0.7，0.3］^T，欲知道最终城乡人口的比例为何，则就是要计算AⁿP，如果最开始的城乡人口的比例为9:1，结果又如何。上述定理中的最后一条就表明，当n趋近于无穷大的时候，AⁿP就等于v，而且与P是无关的。更精妙的地方还在于，这个定理还告诉我们v是一个概率向量，而且它就是特征值1所对应的特征向量。

这个定理的证明已经超出了本书的范围，但可以用之前给出的例子来验证一下它。注意到如果想要计算AⁿP，其实就是要先设法计算矩阵A自乘n次的结果，这时为了计算方便应该先将矩阵A对角化。为此，先求矩阵A的特征多项式，通过其特征多项式便知道矩阵A有两个特征值，一个是1，一个是0.88。根据定理，1必然是该矩阵的特征值。更进一步，特征值1对应的特征向量是［1，5］^T，特征值0.88对应的特征向量是［1，-1］^T。所以知道矩阵对角化时所用的Q和Q^-1分别为

于是可知矩阵A的对角化结果如下：

所以有

然后把值带进去就能算出最终结果如下

之前计算过特征值1对应的一个特征向量是［1，5］^T，特征向量乘以一个系数仍然是特征向量（注意要求最后的特征向量同时是一个概率向量，所以会得到［1/6，5/6］^T，可见上述计算与定理所揭示的结果是完全一致的。

矩阵的极限，其实就是在讨论的存在性，也就是把矩阵自乘m次后，如果结果矩阵中每个元素的极限都存在，就说这个矩阵的极限是存在的。而矩阵极限是否存在可以由下面的定理保证。

定理　矩阵极限存在的充要条件：

（1）|λ|＜1或者λ=1，其中λ是A的任意特征值。

（2）如果λ=1，那么它对应的几何重数等于代数重数。

定理　矩阵极限存在的充分条件：

（1）|λ|＜1或者λ=1，其中λ是A的任意特征值。

（2）矩阵A是可对角化的。