3.3 平稳分布与遍历性：从转移矩阵到 PageRank

3.3 平稳分布与遍历性：从转移矩阵到 PageRank

本节摘要：不设吸收态的马尔可夫链走无穷多步后，各状态的访问占比往往稳定下来——这就是平稳分布。本节给出两把通行证（不可约、非周期）、平稳分布的两种解法、遍历定理的"时间平均等于空间平均"，并以 PageRank 的完整推导与数值实验收官：一条亿万网页的马尔可夫链，其平稳分布决定搜索排序。

问一个看起来天真的问题：把一副洗乱的牌按固定规则反复洗（比如每次把顶牌插到随机位置），洗到无穷多次之后，某张特定牌出现在顶部的频率是多少？再问：一只在房间网络里随机游走的虫子，长期看它在每个房间的停留时间占比是多少？两个问题的答案都叫平稳分布。它回答的是随机过程的"长期画像"问题：单条路径看起来乱走，占比却收敛到确定值。

两把通行证：不可约与非周期

平稳分布不是对所有链都存在且唯一的，通行需要两个条件：

不可约：从任何状态出发都能（以正概率、有限步）到达任何其他状态。直观：状态图连成一片，没有"围墙内的小社会"。违反的典型是吸收链（3.2 节）——一旦进入吸收态就再也出不去，与别的状态断了往来。

非周期：存在某个时刻 n 之后，从状态 i 出发能在任意后续时刻回到 i。周期链的经典反例是"简单交替链"：A、B 两状态每步互换，从 A 出发只能偶数步回到 A。这类链的分布会永远振荡，不收敛。

两证齐备的链称为遍历链，此时三个强结论同时成立：平稳分布存在且唯一；从任意初始分布出发，n 步后分布收敛到平稳分布；对几乎每条样本路径，状态 i 的时间占比收敛到 πᵢ。第三条就是遍历定理，它有个值得刻在脑子里的表述：时间平均 = 空间平均。单条路径跑足够久，与"同时观察无穷多条路径"给出同样的统计——这为第 5 章的蒙特卡洛方法（用单条长链的样本均值估计总体期望）提供了合法性来源。

收敛速度由转移矩阵次大特征值的模决定：越接近一收敛越慢，链有"接近围墙"的结构时（比如两个社区之间只有一条窄桥），这个值逼近一，混合明显变慢。社交网络与马尔可夫链蒙特卡洛采样里遇到的"混合困难"，根源都是它。

解平稳分布：逐点平衡与详细平衡

平稳分布 π 满足 π = πP 与归一化 Σπᵢ = 1。逐点写开是 πⱼ = Σᵢ πᵢpᵢⱼ：进入 j 的概率流等于"各处按占比送出"的总和。直接解线性方程组即可，3.1 节的双状态例子已经演示过。

当链可逆（满足详细平衡）时有更快的机会：πᵢpᵢⱼ = πⱼpⱼᵢ 对一切 i、j 成立——每一对状态之间的流量两两对消。此时 πᵢ ∝ 出边率的倒数，状态空间是图时 πᵢ 正比于节点的度（连接数越多，停留占比越大）。详细平衡是第 5 章 MCMC 方法的命门：构造满足详细平衡的链，平稳分布就是目标分布。记不住全部理论也行，这张"详细平衡 ⇒ 平稳"的传票必须随身携带。

图：从随机游走到平稳分布

PageRank：平稳分布的十亿次商用

背景：搜索引擎要给网页排序，"重要"怎么量化？1998 年前后布林与佩奇给出的回答堪称马尔可夫链最著名的商业应用：把随机游走者放到网页图上，它长期停在各页面的占比就是页面重要性。

建模：想象一个冲浪者，每一步从当前页面等概率地点击一条出链。出链越多，每个链接分到的份额越薄；被指入越多，被访问的机会越大。冲浪者在每个页面上的长期占比，恰是"页面图上随机游走的平稳分布"。

两处工程修正。其一，有些页面没有出链（悬挂节点），游走者会在那里消失——工程处理是把它们视作指向所有页面。其二，真实图常有难以混通的局部结构（蜘蛛网状的小圈子），冲浪者可能长期困在角落。修正办法是阻尼：每一步以概率 s（实践中约 0.85）按链接走，以概率 1 − s 完全随机地跳向任意页面。阻尼等价于在转移矩阵里混入均匀分布，好处有三：图再破碎也立刻不可约、立刻非周期、混合速度有保障（次大特征值被压到 s 以下）。

解读：PageRank 是"重要性"的一种定义而非唯一真理——它度量的是"随机点击流的占比"，与内容质量、时效无关。后续搜索引擎叠加了上百个信号，但"长期占比即排序"的思想框架留存至今。互联网时代的许多排序系统（推荐、影响力度量、网络可靠性分析）都是同一思想换一张图。

数值实验：手搓一个 PageRank

import numpy as np

# 6 个页面，links[i] 为页面 i 的出链列表（模拟一个小型网络）
links = {
    0: [1, 2], 1: [3], 2: [0, 3],
    3: [2, 4, 5], 4: [5], 5: [3],
}
n = 6
s = 0.85                                   # 阻尼系数

P = np.full((n, n), (1 - s) / n)           # 随机跳转打底
for i, outs in links.items():
    if outs:
        for j in outs:
            P[i, j] += s / len(outs)
    else:                                  # 悬挂节点：全域跳
        P[i] += s / n

rank = np.ones(n) / n                      # 初始均匀分布
for _ in range(200):                       # 幂迭代
    rank = rank @ P

print("各页面 PageRank：", np.round(rank / rank.sum(), 4))
# 典型输出：页面 3 与 5 占比最高（被大量指入且互相输血）
# 对比各页入度：PageRank 与"入度排名"接近但不相同——
# 被重要页面指一次，胜过被冷门页面指三次，这正是"投票权重传导"的效果
​

把 s 调到 0.5 再跑：收敛更快，排名结构变化不大；把 s 调到 0.99：收敛变慢，个别页面的排名开始波动。这个对照把"阻尼 = 用少量偏差换收敛稳定性"的工程取舍演示得一目了然。

练一练：三个定位题

题一（判断可逆）：三状态链 A、B、C 排成一圈，只能顺时针走（A 到 B、B 到 C、C 到 A 各以概率一）。它平稳吗？行——均匀分布满足逐点平衡。它可逆吗？不可逆：顺时针流没有反向流对消，详细平衡无从谈起。平稳不等于可逆，可逆是更强的对称性要求；MCMC 需要的只是可逆（详细平衡），因为它好构造。

题二（周期检出）：偶数步往返链在 3.3 节提过。更隐蔽的周期藏在"两点一桥"结构里：两个团块之间仅一条双向窄桥，路径每过一次桥换一个团块，团块内逗留时长若高度规律，整体可能出现近似周期。处理办法是 3.3 节 PageRank 的阻尼技巧——混入小概率的全局跳转，周期性被立刻打散。这一招在 MCMC 里叫"惰性取步"（以一半概率原地不动），专治近似周期。

题三（时间平均要跑多久）：遍历定理只说"最终收敛"，没说多久。经验估算用有效样本量：先估计自相关时间 τ（相邻状态相关拖长的倍数），时间平均的误差约按 √(τ/n) 缩水。若 τ 是一百、想要百分之一的精度，名义步数就得百万级——遍历定理的支票要配混合速度的利息，这正是第 5 章 MCMC 报告必须附自相关诊断的原因。

本节要点回顾

• 平稳分布 = 长期访问占比，存在唯一需要不可约加非周期两把通行证。
• 遍历定理：时间平均等于空间平均，单条长链可以代替无穷多条路径做统计。
• 收敛速度看次大特征值：接近围墙的结构让混合变慢。
• 详细平衡给出快捷解：流量两两对消时平稳分布正比于度的倒数关系，MCMC 的命门。
• PageRank = 网页图随机游走的平稳分布，阻尼因子换图连通性与混合速度。

长期行为讲完，下一节把"每步一拍"的时间轴拆掉：转移随时可能发生的连续时间链与生灭过程。