马尔可夫链：只记得现在的随机游走
本文基于模型知识整理（生成时未联网核对），收敛定理（遍历性）建议对照 Norris《Markov Chains》复核。
一句话定义
马尔可夫链是"下一步只依赖当前状态"的随机过程（马尔可夫性/无记忆性）：离散状态链由转移矩阵 P 描述（$P_{ij}=P(X_{t+1}=j|X_t=i)$）；不可约+非周期（遍历）的链收敛到唯一的平稳分布 π（满足 πP=π）——无论从哪出发，走得够久都到达同一长期分布。
为什么重要
它是随机过程的"氢原子"（最简非平凡模型）：PageRank（平稳分布=网页权重）、隐马尔可夫模型（语音/基因序列）、强化学习的环境模型（kp-030 姊妹篇）、以及最重要的——MCMC（用马尔可夫链采样任意复杂分布，贝叶斯推断 kp-022 的计算引擎）。"无记忆+长期收敛"两个性质撑起半座应用山。
前置知识
kp-003（条件概率）、kp-010（分布演化）、矩阵乘法。
核心概念
- 马尔可夫性：$P(X_{t+1}|X_t,\dots,X_0)=P(X_{t+1}|X_t)$——历史被当前状态完全总结（kp-002 条件概率的结构化应用）。
- 转移矩阵 P：行随机（每行和=1）；t 步转移概率 $P^{(t)}=P^t$（矩阵幂，kp-007 的线性代数接口）——"n 步后的分布 $\mu_t=\mu_0P^t$"。
- 平稳分布：πP=π（左特征向量，特征值 1，kp-030 姊妹篇）——进入平稳后每步分布不再变化；PageRank 的排名向量即 web 图的平稳分布。
- 遍历性（收敛条件）：不可约（任意状态可达任意状态）+ 非周期（不陷入固定循环）⇒ 唯一平稳分布且 $\mu_0P^t\to\pi$ 对一切初值成立——链的"大数定律"（时间平均→空间平均 kp-014 的马尔可夫版）。
- 细致平衡：$\pi_ip_{ij}=\pi_jp_{ji}$——满足者必以 π 为平稳分布（可逆链）；MCMC 的 Metropolis-Hastings 就是反向工程构造满足细致平衡的链（kp-027：想要哪个 π，就造一条以它为平稳分布的链）。
- 吸收链：有状态一旦进入无法离开（赌徒破产问题）——吸收概率与期望时间的计算。
原理与机制
为什么无记忆性反而强大：把"任意历史依赖"压缩为"当前状态依赖"——只要状态设计得当（信息充分，kp-022 的马尔可夫性讨论），模型参数只有 n×n 个转移概率（vs 全历史的指数级）；这是可计算性与表达力的黄金交换。
为什么链会收敛：不可约+非周期使 $P^t$ 各行趋于 π（混合）——信息在状态间充分混合后，初始位置的影响被指数冲淡（混沌的良性版）。周期链会永远振荡（不收敛但平稳分布仍存在）——"遍历"条件正是为了排除振荡。
MCMC 的反向工程：给定目标分布 π（如贝叶斯后验），构造转移核满足细致平衡 πp_{ij}=πp_{ji}（接受率公式保证）——链的平稳分布自动=π；跑足够久，访问频率≈π（kp-027 的 MCMC 采样原理）。贝叶斯推断的计算瓶颈被马尔可夫链理论解锁（kp-022 的"现代贝叶斯成本"正是这里买单）。
图示
马尔可夫性: P(X_{t+1}|历史) = P(X_{t+1}|X_t)
转移: P 行随机 ; n步后分布 μ_t = μ₀Pᵗ
平稳分布: πP = π (左特征向量, λ=1)
遍历(不可约+非周期): μ₀Pᵗ → π 对一切初值
细致平衡: πᵢp_{ij}=πⱼp_{ji} ⇒ 平稳 (MCMC 构造原理)
PageRank: web 图随机游走的平稳分布 = 排名直观类比
马尔可夫链像"只看当前棋盘落子的棋手"：不管这盘棋怎么走到这一步，下一步策略只取决于现在的局面——局面信息足够时历史确实可丢。平稳分布像"一家老店的人口结构"：人来人往（转移），多年后社区构成稳定（π）——不管你第一天带来多少老乡。
实例或案例
- PageRank：随机游走+传送（保证不可约非周期）的平稳分布——kp-026 线代姊妹篇的算法化身。
- MCMC 采贝叶斯后验：Metropolis-Hastings/Gibbs——kp-022 的高维引擎。
- 文本生成（n-gram）：下一个词只依赖前 n−1 个词——语言模型的马尔可夫祖师爷（现代 LLM 的远祖 kp-031）。
常见误区
- 误区一："马尔可夫链的极限分布随便选初值都立即适用"。收敛需要遍历（不可约+非周期）；周期链振荡、可约链按初始连通块收敛到不同分布。
- 误区二："平稳分布=每步分布不变=状态不变"。分布不变（π），状态仍每步随机跳——"人流动但人口结构稳"。
- 误区三："有限历史依赖=马氏"。k 阶依赖可折成状态=最近 k 步组合的马氏链（状态空间膨胀）——马氏性是建模选择不是天然性质。
与其他知识点的关系
自测题
- 两状态链 P=[[0.9,0.1],[0.2,0.8]]：求平稳分布。
答：πP=π 且和为 1 → π=(2/3, 1/3)（长期 2/3 时间待在状态 1）。
- 为什么 PageRank 要加"传送项"？
答：保证不可约+非周期（悬挂页/环造成病态）——遍历性是平稳分布存在唯一的门票。
- MCMC 如何"制造"目标分布的样本？
答：构造以目标为平稳分布的转移核（细致平衡公式），跑链至混合后按访问频率取样——分布从链的长期行为中"结晶"。
延伸阅读
- Norris《Markov Chains》（理论标准教材）。
- Grinstead & Snell《Introduction to Probability》马尔可夫章（免费电子书）。
- 《Deep Learning》§16.5 / MacKay 第 29 章（MCMC 接口）。