MathLabs

概率与统计

随机过程与马尔可夫链

随时间演化的随机状态序列,其中马尔可夫链只依赖于当前状态。

直观如果明天只在乎今天,你能把未来预测到多远?

设想一只青蛙在池塘的荷叶间跳来跳去,或一枚棋子在棋盘上逐格移动,或明天的天气在晴天和雨天之间切换。在每种情形中都存在一个状态(哪片荷叶、哪个格子、哪种天气),它在每个时钟节拍都会变化,而这种变化不是预先固定的——它是随机的。随机过程就是一族按时间 n=0,1,2,…n=0,1,2,\dots 编号的随机变量 Xn∈SX_n \in S,每个时刻对应一个随机状态。青蛙的跳跃,以及大量现实系统——基因突变、排队到达的顾客、交易所里跳动的价格、点击链接的网页浏览者——从这个意义上说都是随机过程。马尔可夫链是一种特殊且极为有用的情形:青蛙很健忘,下一次跳跃的概率只取决于它当前所在的荷叶,而与它是如何七绕八绕到达那里的路径无关。

交互式有向图,展示马尔可夫链的状态与转移概率。
一张有向状态图:每个节点是一个状态,每条带标签的箭头是一个转移概率。切换高亮节点可以看到,无论当前处于哪个状态,只有从它出发的箭头决定链接下来去往何处——路径中更早之前的部分完全不重要。

大学马尔可夫性、转移矩阵与平稳分布

定义: 马尔可夫链

设 SS 为一个可数的状态集合,n=0,1,2,…n=0,1,2,\dots 时取值于 SS 的随机过程记为 Xn∈SX_n \in S。称该过程为马尔可夫链,若它具有马尔可夫性:对任意状态选取与任意 nn 都有 P(Xn+1∣Xn,…,X0)=P(Xn+1∣Xn)P(X_{n+1}\mid X_n,\dots,X_0)=P(X_{n+1}\mid X_n)。换言之,一旦知道了 XnX_n,整个过去 X0,…,Xn−1X_0,\dots,X_{n-1} 就不再提供关于 Xn+1X_{n+1} 的任何额外信息——当前状态就是全部历史的一个充分概括。

P(Xn+1∣Xn,…,X0)=P(Xn+1∣Xn)P(X_{n+1}\mid X_n,\dots,X_0)=P(X_{n+1}\mid X_n)

当状态空间有限(或可数)且链是时齐的,这种随机性完全由单个转移矩阵 PP 捕捉,其元素为 Pij=P(Xn+1=j∣Xn=i)P_{ij}=P(X_{n+1}=j\mid X_n=i)——即链当前处于 ii 时跳到状态 jj 的概率。由于从任意状态出发链都必须跳到某处,PP 的每一行都是一个概率分布:非负且和为一,∑j∈SPij=1\sum_{j\in S} P_{ij}=1。具有这种行和为一性质的矩阵称为行随机矩阵。将 nn 步转移与 mm 步转移相乘恰好对应于矩阵乘法,即查普曼-科尔莫戈罗夫方程 P(n+m)=P(n)P(m)P^{(n+m)}=P^{(n)}P^{(m)},因此从分布 μ0\mu_0 出发经过 nn 步后处于各状态的概率就是 μ0Pn\mu_0 P^n。

Pij=P(Xn+1=j∣Xn=i)P_{ij}=P(X_{n+1}=j\mid X_n=i)

SS 上的概率分布 π\pi 称为平稳分布,若它是该动力学的不动点:πP=π\pi P=\pi,并满足 ∑i∈Sπi=1\sum_{i\in S}\pi_i=1 与 πi≥0\pi_i\ge0。一旦链在某个时刻的分布等于 π\pi,此后每个时刻它都等于 π\pi——尽管每只青蛙仍在随机跳跃,但每片荷叶上青蛙的总数在整体上不再变化。求 π\pi 归结为求解一个线性方程组,而下面的基本定理正是把这一点变成了对存在性、唯一性与收敛性的保证。

πP=π\pi P=\pi
对马尔可夫链进行分类的关键性质
性质定义结论
不可约任意状态都能以正概率到达任意其他状态该链(至多)有一个平稳分布
非周期回到某状态的可能返回时刻的最大公约数为1PnP^n 的幂逐项收敛,而不仅是平均收敛
常返从状态 ii 出发,链以概率1返回 ii在有限不可约链上这总是自动成立
定理: 有限马尔可夫链基本定理

若有限状态空间 SS 上的马尔可夫链是不可约且非周期的,则存在唯一的平稳分布 π\pi,满足 πP=π\pi P=\pi、对每个状态 πi>0\pi_i>0,且 lim⁡n→∞Pn=1 π\lim_{n\to\infty}P^n=\mathbf 1\,\pi——即无论初始分布如何,PnP^n 的每一行当 n→∞n\to\infty 时都收敛到 π\pi。

为什么成立?

这正是马尔可夫链之所以有用的原因:它表明一个随机演化系统的长期行为会稳定到一个单一的、可预测的模式,并且会忘记自己的出发点,同时准确告诉我们这个模式是什么(转移动力学的唯一不动点)。

证明

存在性与唯一性。由于 PP 是行随机矩阵,全1向量是特征值为1的右特征向量,故1也是 PP 的特征值(矩阵与其转置共享特征值),从而存在相应的左特征向量 π\pi 满足 πP=π\pi P=\pi。不可约性意味着 PP 是一个强连通图的转移矩阵,因此可以应用佩龙-弗罗贝尼乌斯定理:特征值1是单重的(重数为一),且其特征向量可取为严格为正,归一化使各分量之和为1后即得唯一性。

收敛性。非周期性加上不可约性意味着 PP 的所有其他特征值 λ\lambda 都满足 ∣λ∣<1|\lambda|<1(这正是周期性会破坏的部分:周期链恰好在单位圆上有额外的特征值,例如 −1-1,它永远不会衰减)。将任意初始分布 μ0\mu_0 用 PP 的特征基展开,沿 π\pi 方向的分量(特征值1)永远保持不变,而其余每个分量在第 nn 步都被乘以 λn\lambda^n,以几何速度衰减到零。

结合这两步,μ0Pn\mu_0 P^n 收敛到唯一的特征值1分量,即恰为 π\pi;由于这对任意初始分布 μ0\mu_0(包括每个点质量,即单位矩阵的每一行)都成立,故 PnP^n 的每一行都如所述收敛到 π\pi。

定理: PageRank 作为随机浏览者的平稳分布

设 JJ 为 N×NN\times N 全1矩阵(NN 为网页数),PP 为行随机的链接矩阵(网页 ii 平均链接到它指向的每个网页;没有出链的网页被均匀发送到所有网页)。对任意阻尼系数 d∈(0,1)d\in(0,1),谷歌矩阵 G=dP+(1−d)1NJG=dP+(1-d)\tfrac1N J 是一个不可约、非周期马尔可夫链的转移矩阵,因此由上述基本定理,它存在唯一的平稳分布 π\pi,满足 π=π(dP+(1−d)1NJ)\pi=\pi\Big(dP+(1-d)\tfrac1N J\Big)——这个 π\pi 正是 PageRank 向量,幂迭代算法 πk+1=πkG\pi_{k+1}=\pi_k G 从任意初始猜测出发都收敛于它。

为什么成立?

这把「重要网页会被其他重要网页链接」这一模糊想法,变成了一个保证有唯一解的良定义不动点问题,并解释了为何简单地反复「沿链接传播权重」(幂迭代)必定收敛而不是振荡或发散。

证明

不可约性。由于 1−d>01-d>0,GG 的每个元素都严格为正(Gij≥(1−d)/N>0G_{ij}\ge(1-d)/N>0),因此从任意网页出发都能以正概率一步直接跳到任意其他网页——底层图显然是强连通的,故 GG 不可约。

非周期性。一个每个状态都能直接到达每个状态(包括自身,因为 Gii>0G_{ii}>0 也成立)的链,其可能的返回时长涵盖了所有 1,2,3,…1,2,3,\dots,它们的最大公约数为1;故 GG 非周期。

存在性、唯一性与收敛性。GG 按构造是行随机矩阵(两个行随机矩阵 PP 与 J/NJ/N 的凸组合 dP+(1−d)1NJdP+(1-d)\tfrac1N J 仍是行随机矩阵),且如上所示它不可约且非周期,故有限马尔可夫链基本定理可直接应用:存在唯一的平稳分布 π\pi 满足 π=π(dP+(1−d)1NJ)\pi=\pi\Big(dP+(1-d)\tfrac1N J\Big),且 GnG^n 逐项收敛到每一行都等于 π\pi 的矩阵。

幂迭代。由于对任意初始分布 π0\pi_0 都有 πk=π0Gk\pi_k=\pi_0G^k,且 GkG^k 的每一行当 k→∞k\to\infty 时都收敛到 π\pi,故加权平均 π0Gk\pi_0G^k 也收敛到 π\pi——这正是为何从任意初始排名(通常取均匀分布)出发反复应用 πk+1=πkG\pi_{k+1}=\pi_k G 必定收敛到真实 PageRank 向量的原因。

大学实际应用与典型例题

马尔可夫链为大量「已知现在即可忘记过去」是合理近似的系统建模。谷歌最初的 PageRank 算法通过点击链接的随机浏览者的平稳分布(上文已证明)对网页排名。在生物学中,DNA 序列和蛋白质折叠路径被建模为核苷酸或构象上的马尔可夫链。在金融与运筹学中,排队系统(顾客在收银台等待)和库存水平被作为马尔可夫链追踪,用以计算长期等待时间和缺货概率。在语音识别与自然语言处理中,隐马尔可夫模型将音素或词性标签链接起来。而在计算机科学中,MCMC(马尔可夫链蒙特卡罗)算法构造一个以难以直接采样的目标分布为平稳分布的马尔可夫链,再通过模拟它来抽取近似样本。

例题: 天气的平稳分布

一个简化的天气模型有两个状态,晴天和雨天,转移矩阵为 P=(0.90.10.50.5)P=\begin{pmatrix}0.9&0.1\\0.5&0.5\end{pmatrix}(第1行 = 从晴天出发,第2行 = 从雨天出发;所以从晴天出发以概率 0.90.9 保持晴天,以概率 0.10.1 变为雨天)。求平稳分布 π=(π1,π2)\pi=(\pi_1,\pi_2)。

解答

平稳方程为 πP=π\pi P=\pi,即 0.9π1+0.5π2=π10.9\pi_1+0.5\pi_2=\pi_1 与 0.1π1+0.5π2=π20.1\pi_1+0.5\pi_2=\pi_2,连同 π1+π2=1\pi_1+\pi_2=1。

第一个方程化简为 0.5π2=0.1π10.5\pi_2=0.1\pi_1,即 π2=0.2π1\pi_2=0.2\pi_1(第二个方程给出相同关系,这是必然的,因为 πP−π\pi P-\pi 的两行是相关的)。

代入归一化条件:π1+0.2π1=1\pi_1+0.2\pi_1=1,故 1.2π1=11.2\pi_1=1,得 π1=5/6\pi_1=5/6、π2=1/6\pi_2=1/6。

因此 π=(5/6, 1/6)\pi=(5/6,\,1/6)——长期来看,这条天气链有 5/65/6 的时间处于晴天。这符合直觉:状态1(晴天)比状态2(雨天,留下概率 0.50.5)「更粘」(留下概率 0.90.9),因此链大部分时间都停留在粘性更强的状态。

例题: 三页网络的 PageRank

一个微型网络有三个网页 A,B,CA,B,C:网页 AA 平均链接到 BB 与 CC,网页 BB 只链接到 CC,网页 CC 只链接回 AA:P(A→B)=P(A→C)=12,P(B→C)=1,P(C→A)=1P(A\to B)=P(A\to C)=\tfrac12,\quad P(B\to C)=1,\quad P(C\to A)=1。将随机浏览者的点击建模为 {A,B,C}\{A,B,C\} 上的马尔可夫链,并求 PageRank 向量 π\pi。

解答

首先检验链是不可约且非周期的:任意网页都能到达任意其他网页(经由 A→B→C→AA\to B\to C\to A),且存在长度为2(A→C→AA\to C\to A)与长度为3(A→B→C→AA\to B\to C\to A)的圈,其最大公约数为1,故基本定理保证存在唯一的平稳分布 π\pi。

逐列写出平衡方程:πA\pi_A 只从 CC 接收流量,πB\pi_B 只从 AA 接收,πC\pi_C 同时从 AA 和 BB 接收:πA=πC,πB=12πA,πC=12πA+πB\pi_A=\pi_C,\quad \pi_B=\tfrac12\pi_A,\quad \pi_C=\tfrac12\pi_A+\pi_B。

前两个方程直接给出 πA=πC\pi_A=\pi_C 与 πB=12πA\pi_B=\tfrac12\pi_A;代入归一化条件 πA+πB+πC=1\pi_A+\pi_B+\pi_C=1 得 πA+12πA+πA=1\pi_A+\tfrac12\pi_A+\pi_A=1,即 52πA=1\tfrac52\pi_A=1。

解得 πA=2/5\pi_A=2/5,故 π=(πA,πB,πC)=(2/5, 1/5, 2/5)\pi=(\pi_A,\pi_B,\pi_C)=(2/5,\,1/5,\,2/5)。网页 AA 与网页 CC 并列最高排名,因为它们各自都从一个只有单一出链、把全部权重都送过来的网页那里获得链接——这正是 PageRank 意在奖励的「投票集中」效应。

马尔可夫性是指,已知当前状态 XnX_n 时,下一个状态 Xn+1X_{n+1} 是:

一个3状态链的转移矩阵每一行必须:

对于转移矩阵 P=(0.90.10.50.5)P=\begin{pmatrix}0.9&0.1\\0.5&0.5\end{pmatrix},哪个向量 π\pi 满足 πP=π\pi P=\pi 与 ∑i∈Sπi=1\sum_{i\in S}\pi_i=1?

在谷歌最初的 PageRank 中,阻尼系数 d<1d<1(混入到每个网页的均匀 1/N1/N 跳转)之所以至关重要,主要是因为它保证了谷歌矩阵是:

参考文献

  1. David A. Levin, Yuval Peres, Elizabeth L. Wilmer (2017). Markov Chains and Mixing Times
  2. Sergey Brin, Lawrence Page (1998). The Anatomy of a Large-Scale Hypertextual Web Search Engine
  3. James R. Norris (1997). Markov Chains