机器学习数学基础 120 章

Markov 链与平稳分布

层级：B｜建议先修：02-04、05-08、05-09

Markov 链描述一个随时间随机变化的状态序列，并假设下一状态在给定当前状态后不再依赖更久远的历史。它是隐 Markov 模型、MCMC 和强化学习的基础。

1. 随机过程与状态序列

随机过程是一族按时间索引的随机变量 {Xt}t≥0\{X_t\}_{t\ge0}。若状态空间有限或可数，且满足一阶 Markov 性质

P(Xt+1=j∣Xt=i,Xt−1,…,X0)=P(Xt+1=j∣Xt=i),P(X_{t+1}=j\mid X_t=i,X_{t-1},\ldots,X_0) =P(X_{t+1}=j\mid X_t=i),

则称为离散时间 Markov 链。

“无记忆”并非下一状态与过去完全无关，而是当前状态已经汇总了预测未来所需的历史信息。

2. 转移矩阵

齐次 Markov 链的转移概率不随时间改变：

Pij=P(Xt+1=j∣Xt=i).P_{ij}=P(X_{t+1}=j\mid X_t=i).

矩阵 PP 每个元素非负，每行和为 1，因此称为行随机矩阵。若状态分布用行向量 μt\boldsymbol\mu_t 表示，则

μt+1=μtP,μt=μ0Pt.\boldsymbol\mu_{t+1}=\boldsymbol\mu_tP, \qquad \boldsymbol\mu_t=\boldsymbol\mu_0P^t.

若采用列向量约定，转移矩阵会转置；必须保持约定一致。

3. Chapman–Kolmogorov 方程

从状态 ii 经过 m+nm+n 步到 jj 的概率可在中间状态 kk 上求和：

Pij(m+n)=∑kPik(m)Pkj(n).P_{ij}^{(m+n)}=\sum_kP_{ik}^{(m)}P_{kj}^{(n)}.

矩阵形式就是

Pm+n=PmPn.P^{m+n}=P^mP^n.

4. 状态的可达与互通

若存在 t≥0t\ge0 使 (Pt)ij>0(P^t)_{ij}>0，称 jj 可从 ii 到达。若 i,ji,j 相互可达，则称互通。

所有状态互通的链称为不可约链。不可约意味着状态空间没有彼此隔绝的闭合部分。

5. 周期性

状态 ii 的周期定义为所有可能返回步数的最大公约数：

d(i)=gcd⁡{t≥1:(Pt)ii>0}.d(i)=\gcd\{t\ge1:(P^t)_{ii}>0\}.

若周期为 1，称为非周期。不可约链中所有状态周期相同。周期大于 1 时，分布可能在若干组状态间振荡而不收敛。

6. 常返与暂态

从某状态出发最终返回该状态的概率为 1，则该状态常返；小于 1 则为暂态。有限不可约 Markov 链的所有状态都是正常返，并存在唯一平稳分布。

7. 平稳分布

若概率向量 π\boldsymbol\pi 满足

π=πP,∑iπi=1,\boldsymbol\pi=\boldsymbol\pi P, \qquad \sum_i\pi_i=1,

则称为平稳分布。若 X0∼πX_0\sim\boldsymbol\pi，那么所有时刻的边缘分布都保持为 π\boldsymbol\pi。

它是 PP 的左特征值 1 对应的归一化非负特征向量。

8. 收敛到平稳分布

对有限、不可约、非周期的 Markov 链，任意初始分布都满足

μ0Pt→π.\boldsymbol\mu_0P^t\to\boldsymbol\pi.

这样的链常称为遍历链。不可约保证能遍历整个状态空间，非周期避免持续振荡。

平稳不等于一定收敛：例如两个状态每步必然互换，平稳分布是 (1/2,1/2)(1/2,1/2)，但从状态 1 出发的边缘分布会来回振荡。

9. 细致平衡与可逆性

若对任意 i,ji,j，

πiPij=πjPji,\pi_iP_{ij}=\pi_jP_{ji},

则称满足细致平衡，链关于 π\pi 可逆。对两边求和可得 πP=π\boldsymbol\pi P=\boldsymbol\pi，所以细致平衡是平稳性的充分条件，但不是必要条件。

Metropolis–Hastings 算法常通过构造细致平衡来保证目标分布平稳。

10. 遍历定理

在适当条件下，即使相邻样本相关，时间平均仍收敛到平稳分布下的期望：

1T∑t=1Tf(Xt)→Eπ[f(X)].\frac1T\sum_{t=1}^Tf(X_t)\to\mathbb E_{\pi}[f(X)].

这正是 MCMC 能用一条 Markov 链估计目标期望的理论基础。

11. 混合时间与谱隙

链从初始分布接近平稳分布需要时间。常用总变差距离衡量

∥μPt−π∥TV.\|\mu P^t-\pi\|_{\mathrm{TV}}.

对可逆有限链，第二大特征值的绝对值与 1 的差（谱隙）常控制收敛速度：谱隙越大，通常混合越快。

12. 易错点

  1. Markov 性质取决于状态如何定义；状态信息不足时过程可能不再 Markov。
  2. 平稳分布是分布不变，不表示样本状态停止变化。
  3. 存在平稳分布不等于从任意初始状态都会收敛到它。
  4. MCMC 样本通常相关，不能把有效样本量直接当作迭代次数。

常见问答

Q1：有限 Markov 链一定有平稳分布吗？
至少存在一个；但若链可约，可能不唯一，且从不同初始状态可收敛到不同闭类。

Q2：为什么转移矩阵有特征值 1？
行和为 1，所以全 1 列向量是右特征向量；相应地，平稳分布是左特征向量。

Q3：不可约和非周期各解决什么问题？
不可约排除互不沟通的状态类；非周期排除固定节奏的循环振荡。

Q4：Markov 链中的“无记忆”是否符合现实？
关键是选择足够丰富的状态。把所需历史摘要纳入状态后，高阶依赖可转成一阶 Markov 表示。

练习

  1. 对 P=[0.80.20.30.7]P=\begin{bmatrix}0.8&0.2\\0.3&0.7\end{bmatrix} 求平稳分布。
  2. 两状态确定性交替链为何不收敛？它是否有平稳分布？
  3. 证明细致平衡蕴含平稳性。
  4. 若初始分布就是 π\pi，说明 tt 步后的分布为何仍是 π\pi。

答案与提示

  1. 解 π1=0.8π1+0.3π2\pi_1=0.8\pi_1+0.3\pi_2 与归一化，得 (0.6,0.4)(0.6,0.4)。
  2. 周期为 2，边缘分布在两个状态间振荡；有平稳分布 (1/2,1/2)(1/2,1/2)。
  3. 对 ii 求和：∑iπiPij=∑iπjPji=πj\sum_i\pi_iP_{ij}=\sum_i\pi_jP_{ji}=\pi_j。
  4. 由 πP=π\pi P=\pi 归纳得 πPt=π\pi P^t=\pi。