马尔可夫链

引入

天气预报说明天有雨，这个预测需要知道过去一周下过几天雨吗？

为什么”无后效性”这样一个简单的假设，能让随机过程变得可计算？

转移矩阵里的每一行加起来为什么必须是 $1$？

正文

定义

马尔可夫链是状态空间中从一个状态转移到另一个状态的随机过程，其核心假设是：下一状态只依赖当前状态，与更早的历史无关。

数学表述：

$$P(X_{n+1}=x\mid X_1=x_1,X_2=x_2,\dots ,X_n=x_n)=P(X_{n+1}=x\mid X_n=x_n)$$

状态空间

$X_i$ 可能取的值构成状态空间 $S$。

类型	特征	例子
有限	状态个数有限	天气（晴/阴/雨）
可数无限	可一一列举	排队人数
连续	不可列举	温度（此时称马尔可夫过程）

马尔可夫性质

定义

给定当前状态 $X_n=x_n$，下一个状态 $X_{n+1}$ 的条件概率仅依赖于当前状态 $X_n$，与之前的状态无关。这一性质称为无后效性。

理解：已知 $X_1=x_1,X_2=x_2,\dots ,X_n=x_n$，但求 $X_{n+1}=x$ 的概率时，只需知道 $X_n=x_n$ 就足够，前面的历史全被”压缩”进了当前状态。

为什么这个假设有用？ 若不用它，计算 $P(X_{n+1})$ 需要用到全部历史，状态数会随步数指数增长。用了它，只需保存当前状态，计算量与步数线性相关。

转移概率与转移矩阵

记一步转移概率

$p_{ij}=P(X_{n+1}=j\mid X_n=i)$

则矩阵 $P=(p_{ij})$ 称为转移矩阵。

定义

转移矩阵描述了有限状态空间 $S$ 上的马尔可夫链 $X_t$ 的一步转移规律。

性质	内容
非负	$p_{ij}\ge 0$
行和为 $1$	${\sum }_j{p}_{ij}=1$

行和为 $1$ 的原因：从状态 $i$ 出发，下一步必然落在某个状态上，所有可能性的概率之和为 $1$。这是”规范性”在转移矩阵上的体现。

$n$ 步转移

若初始分布为行向量 ${\pi }_0$，则

${\pi }_n={\pi }_0{P}^n$

即**$n$ 步转移矩阵就是一步转移矩阵的 $n$ 次幂**。

这个结论来自全概率公式的反复应用：

$P(X_{n+2}=j\mid X_n=i)={\sum }_k{p}_{ik}{p}_{kj}=(P^2{)}_{ij}$

矩阵乘法在这里恰好对应”分情况求和”，这不是巧合，而是矩阵乘法定义的设计初衷。

平稳分布

若存在分布 $\pi$ 满足

$\pi P=\pi$

则称 $\pi$ 为平稳分布。它表示经过足够多步后，状态分布不再变化。

条件	结论
有限状态、不可约、非周期	平稳分布存在且唯一
存在平稳分布	不一定是极限分布

容易混淆的两件事：平稳分布”保持不变”，极限分布”必然收敛到”。前者不保证任意初始分布都收敛到它，后者需要额外的不可约与非周期条件。

应用场景

领域	状态	转移
天气预报	晴/阴/雨	次日天气
网页排序	网页	链接跳转
语音识别	音素	相邻音素
生物序列	碱基	下一个碱基
用户行为	页面	下一次点击

PageRank 就是马尔可夫链的平稳分布：把网页看作状态，链接看作转移，随机游走足够久后停留在各页面的概率，就是排序依据。

常见误区

错误说法	问题
”马尔可夫链没有记忆”	有记忆，但只记当前状态
”转移矩阵列和为 $1$“	行和为 $1$（从某状态出发的概率总和）
“平稳分布一定存在且唯一”	需要不可约与非周期条件
”平稳分布就是极限分布”	概念不同，条件更强才是
”马尔可夫性等价于独立”	相邻状态通常不独立

引出

为什么转移矩阵的行和必须为 $1$，而列和不一定？

若链是周期的，长期分布会怎样？

连续时间的马尔可夫过程如何用微分方程描述？

• 条件概率与全概率公式：转移概率的来源
• 离散型随机变量：分布与期望
• 向量：矩阵乘法的向量视角
• 应用数学：应用数学的整体框架
• 数学：数学学科入口