马尔可夫链

概述

马尔可夫链（Markov Chain）是一种特殊的随机过程，具有”无记忆性”（Memorylessness）的特点——当前状态只与上一状态有关，与更早的历史无关。¹

马尔可夫链在搜索引擎（PageRank）、语音识别、自然语言处理、推荐系统等领域都有广泛应用。

---

马尔可夫性质

定义

设 $\{X_t\}$ 为一个离散时间随机过程，若对任意时刻 $t$ 和任意状态序列 $i_0,i_1,\dots ,i_{t-1},i_t,j$，满足：

$$P(X_{t+1}=j\mid X_t=i_t,X_{t-1}=i_{t-1},\dots ,X_0=i_0)=P(X_{t+1}=j\mid X_t=i_t)$$

则称该过程具有马尔可夫性质（Markov Property）。

直观理解

未来只与现在有关，与过去无关。

这意味着，如果我们知道当前状态 $X_t$，那么关于过去的任何信息都不会帮助我们更好地预测 $X_{t+1}$。

---

马尔可夫链的定义

基本要素

一个马尔可夫链由以下要素定义：

要素	符号	说明
状态空间	$S=\{s_1,s_2,\dots ,s_n\}$	所有可能状态的集合
转移概率矩阵	$P$	$p_{ij}=P(X_{t+1}=s_j\mid X_t=s_i)$
初始分布	$\pi$	${\pi }_i=P(X_0=s_i)$

转移概率矩阵

转移概率矩阵 $P$ 是一个 $n\times n$ 的行随机矩阵（每行和为1）：

$$P=\left(\begin{array}{cccc}{p}_{11}& p_{12}& \cdots & p_{1n}\\ p_{21}& p_{22}& \cdots & p_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ p_{n1}& p_{n2}& \cdots & p_{nn}\end{array}\right)$$

其中 $p_{ij}\ge 0$ 且 ${\sum }_{j=1}^n{p}_{ij}=1$。

---

n步转移概率

Chapman-Kolmogorov方程

从状态 $i$ 经过 $n$ 步到达状态 $j$ 的概率记为 $p_{ij}^{(n)}$。根据Chapman-Kolmogorov方程：

$$p_{ij}^{(n+m)}=\sum _{k\in S}{p}_{ik}^{(n)}\cdot p_{kj}^{(m)}$$

这意味着我们可以利用矩阵乘法来计算多步转移概率：

$$P^{(n)}=P^n$$

即 $n$ 步转移概率矩阵等于转移概率矩阵的 $n$ 次方。

---

稳态分布

平稳分布的定义

若一个概率分布 $\pi$ 满足：

$$\pi P=\pi$$

则称 $\pi$ 为该马尔可夫链的平稳分布（Stationary Distribution）。

极限分布

对于许多马尔可夫链，当 $n\to \infty$ 时，$n$ 步转移概率 $P(X_n=j)$ 趋向于一个与初始状态无关的极限分布 ${\pi }_j$。

遍历定理

遍历定理（Ergodic Theorem）指出：对于不可约、非周期、正常返的马尔可夫链，时间平均趋向于空间平均。

---

状态分类

可达与互通

• 可达：若存在 $n\ge 0$ 使得 $p_{ij}^{(n)}>0$，则称 $j$ 可从 $i$ 可达，记为 $i\to j$
• 互通：若 $i\to j$ 且 $j\to i$，则称 $i$ 与 $j$ 互通，记为 $i\leftrightarrow j$

周期性

状态 $i$ 的周期 $d$ 定义为：

$$d=\gcd \{n\ge 1:p_{ii}^{(n)}>0\}$$

• 若 $d=1$，则状态是非周期的
• 若 $d>1$，则状态是周期的

常返与瞬态

• 常返（Recurrent）：从状态 $i$ 出发，以概率1返回 $i$
• 瞬态（Transient）：从状态 $i$ 出发，存在正概率永不返回 $i$

---

马尔可夫链蒙特卡洛方法（MCMC）

马尔可夫链的一个强大应用是马尔可夫链蒙特卡洛方法，用于从复杂分布中采样。

Metropolis-Hastings算法

1. 从当前状态 $x$ 出发
2. 从提议分布 $q(x^{\prime }\mid x)$ 采样候选状态 $x^{\prime }$
3. 计算接受率：$\alpha =\min \left(1,\frac{\pi (x^{\prime })q(x\mid x^{\prime })}{\pi (x)q(x^{\prime }\mid x)}\right)$
4. 以概率 $\alpha$ 接受 $x^{\prime }$，否则保持 $x$

Gibbs采样

Gibbs采样是Metropolis-Hastings的特殊情况，每次只更新一个变量：

$$x_i^{(t+1)}\sim P\left(X_i\mid X_{-i}^{(t)}\right)$$

---

应用实例：PageRank

Google的PageRank算法本质上就是一个马尔可夫链。

基本思想

• 网页的重要性取决于指向它的网页数量和质量
• 用户随机浏览网页的行为可以用马尔可夫链建模
• PageRank值就是该马尔可夫链的平稳分布

数学表述

设网页 $i$ 的PageRank为 $PR(i)$，$L_j$ 为页面 $j$ 的出链数，则：

$$PR(i)=\frac{1-d}{N}+d\sum _{j\in B_i}\frac{PR(j)}{L_j}$$

其中 $d$ 是阻尼因子（通常取0.85），$B_i$ 是指向 $i$ 的页面集合。

---

应用实例：天气模型

考虑一个简化的天气模型：

状态	晴	雨
晴	0.7	0.3
雨	0.4	0.6

转移概率矩阵：

$$P=\left(\begin{array}{cc}0.7& 0.3\\ 0.4& 0.6\end{array}\right)$$

稳态分布计算

设稳态分布为 $({\pi }_1,{\pi }_2)$，满足：

$$\{\begin{array}{l}{\pi }_1=0.7{\pi }_1+0.4{\pi }_2\\ {\pi }_1+{\pi }_2=1\end{array}$$

解得：${\pi }_1=\frac{4}{7}\approx 0.571$，${\pi }_2=\frac{3}{7}\approx 0.429$

这意味着长期来看，约57.1%的时间是晴天，42.9%的时间是雨天。

---

与其他模型的关系

隐马尔可夫模型（HMM）

隐马尔可夫模型是马尔可夫链的扩展，其中状态是”隐藏”的，只能通过观测序列来推断。详见 隐马尔可夫模型。

条件随机场（CRF）

条件随机场是一种判别式模型，用于序列标注任务。相比HMM，CRF可以建模更复杂的依赖关系。详见后续的概率图模型文档。

---

参考

Footnotes

1. 本文档参考了《概率论与数理统计》相关章节和斯坦福CS228课程材料 ↩