第 71 章 Markov 链

前置：非负矩阵与 Perron-Frobenius (Ch17) · 概率论基础 · 矩阵分析 (Ch14)

本章脉络：状态的随机流转 \(\to\) 马尔可夫 (Markov) 性质与转移矩阵 \(P\) \(\to\) 行随机矩阵的定义 \(\to\) 平稳分布 (Stationary Distribution) \(\boldsymbol{\pi}\) 的特征值定义 \(\to\) 状态分类：吸收态、瞬时态与正则链 \(\to\) 核心定理：基本收敛定理（谱半径 1 的主宰） \(\to\) 混合时间 (Mixing Time) 与谱间隔 (Spectral Gap) \(\to\) 吸收 Markov 链的基础矩阵 \(\to\) 应用：Google PageRank 的随机游走解释、棋类游戏的胜率预测、MCMC 采样算法（Metropolis-Hastings）

延伸：马尔可夫链是线性代数的“概率动态化”；它将系统的未来完全封装在当前的概率分布向量中，证明了长期稳定性的本质是算子特征空间的收敛性，是现代随机模拟与强化学习的代数底座

在许多系统中，未来的状态只取决于现在的状态，而与过去无关。这种“无记忆性”被称为 Markov 性质。线性代数为描述这种随机流转提供了完美的工具——转移矩阵（Transition Matrix）。通过研究该矩阵的谱性质，我们可以预见系统在经过无数次随机震荡后，是否会收敛到一个确定的平衡态。本章将介绍这一连接概率逻辑与算子迭代的代数体系。

---

71.1 转移矩阵与平稳分布

定义 71.1 (转移矩阵 \(P\))

对于 \(n\) 个状态的系统，\(P\) 的条目 \(p_{ij}\) 表示从状态 \(i\) 转移到状态 \(j\) 的概率。 性质：\(P\) 是行随机矩阵，即每行元素之和为 1。

定义 71.2 (平稳分布 \(\boldsymbol{\pi}\))

若概率向量 \(\boldsymbol{\pi}\) 满足 \(\boldsymbol{\pi}^T P = \boldsymbol{\pi}^T\)，则称其为平稳分布。 代数本质：它是 \(P\) 对应于特征值 1 的左特征向量。

---

71.2 收敛性与谱间隔

定理 71.1 (马尔可夫链收敛定理)

若 Markov 链是不可约且非周期的（即 \(P\) 是原初矩阵），则对于任何初始分布 \(\mathbf{x}_0\)，均有： $\(\lim_{k \to \infty} \mathbf{x}_0^T P^k = \boldsymbol{\pi}^T\)$ 速度：收敛速度由第二大特征值 \(\lambda_2\) 决定。值 \(1 - |\lambda_2|\) 称为谱间隔。

---

71.3 吸收 Markov 链

技术：基础矩阵 \(N\)

对于包含吸收态（一旦进入就无法离开）的链，转移矩阵可写为 \(\begin{pmatrix} Q & R \\ 0 & I \end{pmatrix}\)。 基础矩阵：\(N = (I - Q)^{-1}\)。 \(N_{ij}\) 的经济意义是：在被吸收前，系统在瞬时态 \(j\) 停留的期望次数。

---

练习题

1. [基础] 判定 \(\begin{pmatrix} 0.5 & 0.5 \\ 0.2 & 0.8 \end{pmatrix}\) 是否为合法的转移矩阵。

参考答案

验证： 1. 所有元素非负（满足）。 2. 第一行和：\(0.5 + 0.5 = 1\)（满足）。 3. 第二行和：\(0.2 + 0.8 = 1\)（满足）。 结论：是一个合法的行随机矩阵。

2. [计算] 求上题矩阵的平稳分布 \(\boldsymbol{\pi}\)。

参考答案

解方程 \(\boldsymbol{\pi}^T P = \boldsymbol{\pi}^T\)： 1. 设 \(\boldsymbol{\pi} = (p, 1-p)^T\)。 2. 第一分量方程：\(0.5p + 0.2(1-p) = p\)。 3. \(0.2 = 0.7p \implies p = 2/7\)。 结论：平稳分布为 \((2/7, 5/7)\)。

3. [性质] 证明：行随机矩阵必有一个特征值为 1。

参考答案

证明： 1. 令 \(\mathbf{1} = (1, 1, \ldots, 1)^T\)。 2. 根据定义，\(P\mathbf{1}\) 的每个分量都是 \(P\) 的一行之和。 3. 既然行和为 1，故 \(P\mathbf{1} = \mathbf{1}\)。 结论：1 是 \(P\) 对应于全 1 特征向量的特征值。

4. [周期性] 判定 \(\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\) 的收敛性。

参考答案

判定： 1. 这是一个周期为 2 的矩阵。 2. 特征值为 \(\{1, -1\}\)。 3. 由于存在模为 1 但不等于 1 的特征值（\(-1\)），幂序列 \(P^k\) 会在两个状态间跳跃而不收敛。 结论：该链不收敛到唯一分布。

5. [吸收链] 设有三个状态 \(\{1, 2, 3\}\)，3 是吸收态。\(Q = \begin{pmatrix} 0.5 & 0.1 \\ 0.1 & 0.5 \end{pmatrix}\)。计算基础矩阵 \(N\)。

参考答案

计算步骤： 1. \(I - Q = \begin{pmatrix} 0.5 & -0.1 \\ -0.1 & 0.5 \end{pmatrix}\)。 2. \(\det = 0.25 - 0.01 = 0.24\)。 3. \(N = (I-Q)^{-1} = \frac{1}{0.24} \begin{pmatrix} 0.5 & 0.1 \\ 0.1 & 0.5 \end{pmatrix} \approx \begin{pmatrix} 2.08 & 0.42 \\ 0.42 & 2.08 \end{pmatrix}\)。 意义：若从状态 1 开始，预期在状态 1 停留约 2.08 次，在状态 2 停留 0.42 次，然后被状态 3 吸收。

6. [收敛速度] 若 \(\lambda_2 = 0.9\)，需要大约迭代多少次才能使误差缩小到 \(1/e\)？

参考答案

估算： 误差按 \(\lambda_2^k\) 衰减。 \(0.9^k \approx e^{-1} \implies k \ln(0.9) \approx -1 \implies k \approx 1/0.1 = 10\)。 结论：大约需要 10 次转移。谱间隔 \(1-\lambda_2\) 越大，收敛越快。

7. [细致平衡] 什么是“细致平衡条件”（Detailed Balance）？

参考答案

定义： \(\pi_i p_{ij} = \pi_j p_{ji}\)。 如果满足此条件，该 Markov 链是可逆的。这保证了平稳分布 \(\boldsymbol{\pi}\) 必然存在，是 MCMC 采样算法（如 Metropolis 算法）构造转移概率的核心准则。

8. [计算] 一个 \(2 \times 2\) 矩阵 \(P\)，两行分别为 \((1-\alpha, \alpha)\) 和 \((\beta, 1-\beta)\)。求其特征值。

参考答案

结论：特征值为 1 和 \(1-\alpha-\beta\)。 这展示了谱间隔如何直接由转移概率的“留存率”决定。

9. [应用] 简述 Markov 链在“打字机猴子”实验中的代数意义。

参考答案

字母序列的生成是一个 Markov 过程。转移矩阵编码了语言的统计特征（如 'q' 后面接 'u' 的概率很高）。通过研究该矩阵的幂，可以计算出随机生成特定单词（如 "HAMLET"）的平均等待时间，这本质上是求解吸收链的期望到达步数。

10. [应用] 什么是 MCMC 中的“燃烧期”（Burn-in）？

参考答案

由于初始分布 \(\mathbf{x}_0\) 可能离平稳分布 \(\boldsymbol{\pi}\) 很远，前期的样本并不反映目标分布。 线性代数证明，经过 \(k \gg 1/(1-|\lambda_2|)\) 次迭代后，状态向量会进入特征值 1 支配的稳定子空间。这一段抛弃掉的初期迭代过程即为燃烧期。

本章小结

Markov 链是线性代数描述随机过程的终极框架：

1. 确定性的概率：它证明了宏观的稳定分布 \(\boldsymbol{\pi}\) 是矩阵谱结构的必然结果，将随机的偶然性升华为代数的必然性。
2. 谱的物理意义：谱间隔 \(1-|\lambda_2|\) 确立了系统“忘却过去”的速度，是评估所有迭代采样算法效率的数学硬指标。
3. 结构的演化：从吸收链的停留时间到正则链的混合时间，矩阵分析为理解现实世界中的排队、检索与扩散过程提供了统一的计算引擎。