深入了解Markov链：原理、应用与优化

Markov链是一种特殊的随机过程。实际应用中，一种常见的随机过程形式为：

也就是说，第n+1步操作Yn+1使得：（到第n步时的）结果X n更新为（到第n+1步时的）结果Xn+1。在很多情况下，第n+1步操作Yn+1是依据（到第n步时的）结果Xn来进行的，而与前面的过程(Xm)m≤n-1无关。例如14.7.3小节中介绍的P´olya罐子实验。

后面我们会说明：P´olya罐子实验并不是一个Markov链（尽管其构成一个鞅）。Markov链中的“链”字是指：一连串实验结果，实验结果是通过式(15.1)中的更新过程生成的，并且，更新过程要保持一种“固定性”，也就是说，更新规则始终保持不变。

15.1.1　人口迁移模型

我们还是从一个例子开始说起。假设人口只在A和B两个城市之间流动，每一年，A城市人口中有p1,1=80%留在A，p2,1=20%移居到B；B城市人口中有p1,2=30%移居到A，p2,2=70%留在B。多年以后，A和B两个城市之间的人口比例如何？假设刚开始时，A和B两个城市之间的人口比例为u0=，并且≥0、≥0、=1。一年后，A和B两个城市之间的人口比例为u1=，而u1和u0之间的关系满足u1=Pu0，其中矩阵

称为转移矩阵[2]。在继续往下分析之前，我们首先要问的一个问题是：为什么=1？总人口既没有增加，也没有减少，只是在两个城市之间相互迁移，显然应该有=1，但是，我们如何从关系式u1=Pu0中看出这一点？注意，是两个向量1=(1,1)T与u1=之间的内积，也就是说，

进一步，我们可以计算：

因此，=1。式(15.4)说明：

•向量1是矩阵P T的特征向量，对应的特征值是λ1=1。

这是Markov链最核心的本质特征。我们的设置使得：转移矩阵P的每一列加起来都等于1，从而保证了上述性质。

于是，我们得到了一个迭代更新过程，每过一年，新的人口比例u n满足：

线性代数有一个关于特征值的重要结论：矩阵P和P T有相同的特征值！因此，λ1=1也是矩阵P的特征值，对应的特征向量为w 1=(0.6,0.4)T。两个特征值之和等于矩阵的迹，也就是说，矩阵对角线元素之和。因此，另一个特征值为λ2=0.5，对应的特征向量为w 2=(1,1)T。初始条件u0可以写为：

其中0≤c≤0.4（注意条件：=1）。将u0代入式(15.5)，可以进一步得到：

当n足够大时，u n≈w 1=(0.6,0.4)T不再发生明显的变化。从任意初始条件u0开始，经过一段时间，人口比例会维持在一个（与初始条件无关的）平衡状态w 1。

注意：在迁徙的过程中，人口总量始终保持不变！也就是说，1T u n=1对于所有的n≥0都成立。因此，我们可以直接得出一个结论：所有特征值的绝对值一定小于等于1（否则1T u∞=∞），并且，至少有一个特征值的绝对值等于1（否则1T u∞=0）。

15.1.2　Markov过程

我们将这个例子拓展到更一般的情况。首先，u0,u1,u2,···对应于：随机过程(Xn)n≥0中各个随机变量X 0,X 1,X 2,···的概率分布：

其中表示：事件X n=xk的概率，也就是说，此外，所有随机变量Xn都在的相同的点集E={x1,x2,x3,···,xN}中进行取值（N可以取无穷大）。

相应地，式(15.2)中的转移矩阵变为[2]：

转移矩阵P中第i行、第i列的元素为：

也就是说，在Xn=xj的条件下，事件X n+1=xi发生的条件概率。因此，转移矩阵P中每一列元素的和都等于1。

根据全概公式，对于i=1,2,3,···,n，都有：

相应的向量表示形式为：

此时，我们称这个随机过程(X n)n≥0是一个Markov链。

由于转移矩阵P中每一列的和都等于1，矩阵P的一个特征值是λ=1，相应的特征向量w=(w1,w2,···,w3)满足：

也就是说，对于i=1,2,3,···,n，都有

特征向量w=(w1,w2,···,w3)是随机变量X n的概率分布的极限情况，也就是说，

我们称w为Markov链的平衡状态[2]。

对式(15.18)稍作变形，可以得到：

注意=1。从xj流入到xi的量为pi,jwj，从xi流出进xk的量为pk,iwi。因此，式(15.20)告诉我们：对于平衡状态w，每一个节点的流入总量等于流出总量。这符合我们的常识，对于每一个节点，正因为总流入等于总流出，才能保持稳定的动态平衡状态，不会随时间而发生变化。Markov链描述的是：节点之间的流入和流出，而总量始终保持不变。总量常常被归一化为“一个单位”，看作是一种概率分布。因此，可以直接得到如下结论：

1.转移矩阵P的所有特征值的绝对值都小于等于1，即|λ(P)|≤1。

2.转移矩阵P的特征值中，至少有一个特征值为1，我们将其称为λ1，对应的特征向量为平衡状态w。

否则，随着时间增加，总量要么变大到无穷，要么变小到零，不会始终保持不变。对转移矩阵P做特征值分解[2]，也就是说，

其中Λ是一个对角矩阵，对角线上的元素为矩阵P的所有特征值λ1,λ2,···,λN。矩阵W=(w 1 w 2···w N)的各个列向量w k分别为矩阵P的特征值λk所对应的特征向量，也就是说，

矩阵S=(s1 s2···s N)的各个列向量s k分别为矩阵P T的特征值λk所对应的特征向量，也就是说，

事实上，和w k分别称为：P的特征值λk所对应的左特征向量和（右）特征向量。矩阵P的特征值分解结果为：

对比式(15.21)，不难发现；

因此，可以进一步得到：(www.xing528.com)

图15.1　在随机游走过程中，每一个内部节点xn都有一半概率变为xn+1，一半概率变为xn-1。(a)边缘节点“有流出”，平衡状态为均匀分布：w=×(11 1···1)T。(b)将边缘节点x1设置为“不流出”，平衡状态w=(10 0···0)T发生了根本变化。

其中λ1=1，w 1=w为平衡状态，s1=1=(1,1,···,1)T。

假设平衡状态唯一，也就是说，对于k=2,3,···,N，都有|λk|＜1，根据式(15.21)，可以进一步得到：

也就是说，矩阵P∞的每一列都是平衡状态w。于是，对于任意的初始概率分布u0，Markov过程的最终概率分布都是：

我们来看一个例子：在图15.1所示的随机游走过程中，每一个内部节点xn都以1/2的概率变为xn+1，另外1/2的概率变为xn-1，不同的边界条件将产生完全不同的结果。图15.1(a)所对应的转移矩阵为：

注意，P T=P，因此，（特征值λ1=1所对应的）平衡状态

为（离散的）均匀分布。

我们稍稍做一下调整，将边缘节点x1设置为“不流出”，称为吸收节点，如图15.1(b)所示。对应的转移矩阵为：

也就是说，将P的第一列调整为(1,0,0,···,0)T。此时，平衡状态

却发生了根本变化，成了一个确定的值。正如图15.1(b)所标注出来的，随机变量Xn一旦取到x1，后续的实验结果立即变成一个确定的值x1，于是，整个随机过程停了下来，变成了一个确定过程。我们可以用14.7.4小节中介绍的停止时间来进行分析。

15.1.3　有限停止时间

事实上，图15.1(b)中的吸收节点x1给出了随机过程的“停止条件”，通过边缘节点x1，我们定义停止时间：

正如我们在14.7.1小节中所讨论的，随机过程(X n)n≤0所对应的集合Ω中的元素ω∈Ω为：

其中xkn表示第n次实验的结果，kn的取值范围为整数1,2,3,···,N。例如，如果第3次实验的结果为x10，那么，下标k3=10。停止时间T是一个随机变量，对ω的函数映射过程T(ω)为：检查ω所对应的一组下标序列k1 k2 k3···在第几位最先出现1，注意，一旦下标出现1以后，后续的下标都是1。例如，当ω=x2,x3,x1,x1,···时，T(ω)=3；当ω=x2,x3,x2,x1,x1,···时，T(ω)=4。当然，存在T=∞的情况，对应的ω为：一串无穷长的、不包含x1的序列，这样的序列有无穷多个，但是其概率为零。一种错误的理解方式是：

注意，上式隐含的一个假设是：随机过程(Xn)n≤0的每一次实验是相互独立的，可是事实上并非如此，Xn+1的取值依赖于X n，转移矩阵P给出了两者之间的关系。因此，式(15.35)中的P(Xn=x1)并不是固定不变的，而是一个关于n的函数：

其中e1=(100···0)T是N阶单位矩阵的第一列，也就是说，第一个元素为1其余元素都为0的N维列向量。当n足够大时，P n u0≈w，其中w=e1见式(15.32)，因此，P(X n=x1)≈ w=1，也就是说，

其中0≤εn≤1，并且，数列{εn}的极限是零！由于序列ω中一旦出现x1，后面的结果都是x1，也就是说，事件T＞n所对应的事件为X n/=x1，因此，P(T＞n)=1P(Xn=x1)=εn。

最终，我们可以计算得到：

这个例子可以推广为一个一般性的结论：

•对于包含有限个节点的Markov链，如果其中含有吸收节点，那么，随机过程(Xn)n≤0几乎确定会停下来^[1]，也就是说，

15.1.4　调和函数与鞅

在继续往下分析之前，我们做一下总结。对于一个随机过程(X n)n≥0，通过式(15.1)中的更新过程，不断生成新的随机变量。例如14.7.3小节中介绍的P´olya罐子实验。在此基础上，Markov链的特殊性还表现在：

1.随机变量Yn+1的作用使得X n+1在不同的状态之间跳转，并不产生新的状态，也就是说，Yn+1的取值只能是{xlxk}，其中k,l=1,2,3,···,N。这些取值正好对应图15.1中的各条边。

2.在Xn=xk的情况下，随机变量Yn+1取值{xlxk}的条件概率

只取决于k和l，而与n无关。所有这些条件概率pl,k构成了转移矩阵P，对应于图15.1中各条边上所标注的转移概率。

Markov链要求式(15.1)中的更新过程保持一种“固定性”，也就是说，更新规则始终不变。P´olya罐子实验中的随机变量(Wn)n≥0（罐子中白球的个数）并不构成一个Markov链，因为条件概率

依赖于n的取值。另一方面，Markov链也不一定构成一个鞅。要构成一个鞅，需要满足：

对于所有的k=1,2,3,···,N都成立。根据条件期望的定义：

因此，一个Markov链构成鞅的条件为：

对于k=1,2,3,···,N都成立，也就是说，向量(x1,x2,···,xN)T是：矩阵P T的与特征值λ=1相对应的特征向量。

一般情况下，x1,x2,···,xN并不满足上述条件，但是，可以通过函数f(x)使得一组映射结果{f(xk)}满足鞅的成立条件，也就是说，

对于所有的k=1,2,3,···,N都成立。我们将使得式(15.45)成立的函数称为调和函数。显然，f(x)=1是一个调和函数，因为向量(1,1,1,···,1)T是矩阵P T的与特征值λ=1相对应的特征向量。

当然，与P T的特征值λ=1相对应的特征向量可能并不唯一。例如：对于下面的转移矩阵

还存在新的调和函数：

其中A为x轴上的一个（任意）区间，这个区间包含点x1和x2，但是不包含点x3和x4。区间为A的补集，也就是说，x轴上“剩余”的部分。参数c1和c2是两个任意实数。当c1=c2=1时，式(15.47)就变成了f(x)=1。经过调和函数映射，随机过程(f(Xn))

n≥0构成一个鞅，相应的σ-代数Fn=σ(Xk:k≤n)参见14.7.1小节中的定义。