马尔可夫链理论基础

概述

马尔可夫链（Markov Chain）是时间和状态都离散的一类随机过程，是概率论与随机过程中最重要的研究对象之一。¹马尔可夫链的核心特征是马尔可夫性质：已知当前状态，未来条件独立于过去。

$$P(X_{t+1}=j\mid X_0=i_0,X_1=i_1,\dots ,X_t=i)=P(X_{t+1}=j\mid X_t=i)$$

这一性质使得马尔可夫链在建模具有”短记忆”特性的系统时极为有用，在物理、金融、生物信息学、自然语言处理等领域都有广泛应用。

---

马尔可夫链的基本定义

形式化定义

定义（离散时间马尔可夫链）：设 $\{X_t{\}}_{t=0}^{\infty }$ 为一列取值于可数状态空间 $\mathcal{S}$ 的随机变量。若对任意时刻 $t\ge 0$ 和任意状态序列 $i_0,i_1,\dots ,i,j\in \mathcal{S}$，满足：

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

则称 $\{X_t\}$ 为离散时间马尔可夫链。

转移概率与转移矩阵

转移概率定义为：

$$p_{ij}^{(t)}=P(X_{t+1}=j\mid X_t=i)$$

若对所有 $t$ 都有 $p_{ij}^{(t)}=p_{ij}$，则称该马尔可夫链是时间齐次的。本文主要讨论时间齐次马尔可夫链。

转移矩阵（或称为随机矩阵）为：

$$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$ 满足：

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

n步转移概率

根据Chapman-Kolmogorov方程，$n$步转移概率满足：

$$p_{ij}^{(n+m)}=\sum _k{p}_{ik}^{(n)}{p}_{kj}^{(m)}$$

用矩阵形式表示为：

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

其中 $P^{(n)}$ 是 $n$ 步转移矩阵。

---

状态的分类

可达与互通

可达：若存在 $n\ge 0$ 使得 $p_{ij}^{(n)}>0$，则称状态 $i$ 可达状态 $j$，记作 $i\to j$。

互通：若 $i\to j$ 且 $j\to i$，则称 $i$ 与 $j$ 互通，记作 $i\leftrightarrow j$。

互通关系是一种等价关系，它将状态空间划分为若干通信类。

状态的基本类型

类型	定义	性质
常返态	$f_{ii}=1$，其中 $f_{ii}$ 是返回概率	无限次返回，几乎必然
瞬变态	$f_{ii}<1$	最终离开，可能有限次返回
周期态	$\gcd \{n:p_{ii}^{(n)}>0\}=d>1$	返回时间受周期限制
非周期态	周期 $d=1$	返回时间无周期性约束

不可约性

若状态空间 $\mathcal{S}$ 中的任意两个状态都互通，则称该马尔可夫链是不可约的。不可约性意味着系统是”连通”的，从任意状态出发都可以到达任意其他状态。

---

稳态分布

稳态分布的定义

定义：若概率分布 $\pi =({\pi }_1,{\pi }_2,\dots )$ 满足：

$$\pi P=\pi$$

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

从代数角度看，稳态分布是转移矩阵 $P$ 的左特征向量，对应特征值 $\lambda =1$。

稳态分布的存在性与唯一性

定理（Perron-Frobenius）：对于任意不可约的有限状态马尔可夫链，稳态分布 $\pi$ 存在且唯一。

对于无限状态空间的情况，需要附加正常返条件：

定理：不可约的马尔可夫链存在唯一稳态分布的充要条件是所有状态都是正常返的。

稳态分布的计算

迭代法：从任意初始分布 ${\pi }^{(0)}$ 出发，迭代计算：

$${\pi }^{(n+1)}={\pi }^{(n)}P$$

当 $n\to \infty$ 时，${\pi }^{(n)}$ 收敛到稳态分布（前提是链不可约且非周期）。

特征值分解法：对转移矩阵 $P$ 进行特征值分解：

$$P=Q\Lambda Q^{-1}$$

稳态分布对应于特征值 1 的左特征向量。

---

收敛性与混合时间

遍历定理

定理（遍历定理）：对于不可约且正常返的马尔可夫链，时间平均几乎必然收敛到空间平均：

$$\frac{1}{n}\sum _{t=0}^{n-1}f(X_t)\stackrel{a.s.}{\to }\sum _i{\pi }_{i}f(i)$$

收敛速率与谱隙

定理（收敛速率）：设马尔可夫链不可约、非周期，则存在常数 $\rho \in (0,1)$ 和 $C$ 使得：

$$\Vert {\pi }^{(n)}-\pi {\Vert }_1\le C{\rho }^n$$

收敛速率由谱隙（spectral gap）决定：

$${\gamma }^{\ast }=1-{\lambda }_2$$

其中 ${\lambda }_2$ 是转移矩阵 $P$ 的第二大特征值（按模）。

谱隙越大，收敛越快。

混合时间

定义：混合时间 ${\tau }_{ϵ}$ 定义为：

$${\tau }_{ϵ}=\min \left\{n:\underset{i}{\max }\Vert P^n(i,\cdot )-\pi {\Vert }_1\le ϵ\right\}$$

混合时间与谱隙的关系：

$${\tau }_{ϵ}\le \frac{\log (1/ϵ)}{{\gamma }^{\ast }}+1$$

---

可逆性与详细平衡

可逆马尔可夫链

定义：若存在概率分布 $\pi$ 满足详细平衡条件（Detailed Balance Equation）：

$${\pi }_i{p}_{ij}={\pi }_j{p}_{ji},\forall i,j$$

则称该马尔可夫链是可逆的。

详细平衡条件是稳态条件 $\pi P=\pi$ 的充分条件。

细致平衡方程的意义

详细平衡条件可以理解为”流”：从 $i$ 到 $j$ 的概率流等于从 $j$ 到 $i$ 的概率流：

$$\text{flow}(i\to j)={\pi }_i{p}_{ij}={\pi }_j{p}_{ji}=\text{flow}(j\to i)$$

典型可逆链示例

名称	转移概率	稳态分布
随机游走	$p_{ij}=1/(2d)$	均匀分布
Metropolis-Hastings	$\min (1,{\pi }_j/{\pi }_i)$	$\pi$
Gibbs采样	条件概率	$\pi$

---

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

Metropolis-Hastings算法

算法步骤：

1. 从提议分布 $q(j\mid i)$ 抽取候选状态 $j$
2. 计算接受概率：$\alpha =\min \left(1,\frac{{\pi }_{j}q(i\mid j)}{{\pi }_{i}q(j\mid i)}\right)$
3. 以概率 $\alpha$ 接受候选状态，否则保持当前状态

收敛性：Metropolis-Hastings算法构造的马尔可夫链以目标分布 $\pi$ 为稳态分布。

Gibbs采样

当条件分布 $p(x_i\mid x_{-i})$ 易于采样时，Gibbs采样是一种高效的MCMC方法：

def gibbs_sampling(target_dist, n_samples, n_vars):
    """Gibbs采样"""
    sample = np.zeros(n_vars)
    samples = []
    
    for _ in range(n_samples):
        for i in range(n_vars):
            # 从条件分布 p(x_i | x_{-i}) 采样
            sample[i] = sample_conditional(i, sample, target_dist)
        samples.append(sample.copy())
    
    return np.array(samples)

MCMC与深度学习的联系

MCMC方法在深度学习中有多方面应用：

1. 贝叶斯神经网络：使用MCMC进行后验采样 贝叶斯神经网络
2. 能量基模型：使用MCMC进行采样生成 能量基模型
3. 扩散模型：将生成过程视为MCMC 扩散模型

---

高阶马尔可夫链与隐马尔可夫模型

高阶马尔可夫链

标准马尔可夫链只依赖前一个状态。$k$ 阶马尔可夫链依赖前 $k$ 个状态：

$$P(X_{t+1}=j\mid X_t,X_{t-1},\dots )=P(X_{t+1}=j\mid X_t,X_{t-1},\dots ,X_{t-k+1})$$

高阶马尔可夫链可以通过状态空间扩张转化为一阶马尔可夫链。

隐马尔可夫模型（HMM）

隐马尔可夫模型是状态不可直接观测的马尔可夫链，见 隐马尔可夫模型。

---

与深度学习的联系

注意力机制作为马尔可夫链

2025年的研究表明，Transformer中的注意力机制可以解释为离散时间马尔可夫链。²

具体来说，注意力矩阵 $A$ 可以视为转移矩阵，注意力分数传播等价于马尔可夫链的状态转移。详见 注意力机制的马尔可夫链理论。

Transformer与马尔可夫数据

研究表明，固定深度的Transformer可以有效建模任意阶的马尔可夫数据。³这一发现揭示了Transformer在处理序列数据时的理论基础。

LLM作为马尔可夫链

大型语言模型可以被视为在词元（token）空间上的马尔可夫链，生成过程等价于在转移矩阵上的采样。⁴

---

参考文献

Footnotes

1. Norris, J. R. (1998). Markov Chains. Cambridge University Press. ↩

2. Engel et al. (2025). “Attention (as Discrete-Time Markov) Chains.” arXiv:2507.17657. ↩

3. Transformers on Markov Data (2024). “Transformers on Markov Data: Constant Depth Suffices.” arXiv:2407.17686. ↩

4. Men et al. (2024). “Large Language Models as Markov Chains.” arXiv:2410.02724. ↩