====== 第五章 状态的分类与极限分布 ======

===== 5.1 引言 =====

本章深入研究马尔可夫链状态空间的精细结构，系统讨论状态的分类方法、极限行为以及平稳分布的理论。这些内容构成了马尔可夫链理论的核心，也是应用马尔可夫链解决实际问题的基础。

===== 5.2 状态分类的深入分析 =====

==== 5.2.1 常返态的进一步分类 ====

**定义5.1（平均返回时间）** 对于常返态 $i$，定义**平均返回时间**：
$$\mu_i = E[T_i | X_0 = i] = \sum_{n=1}^{\infty} n f_{ii}^{(n)}$$

**定义5.2（正常返与零常返）** 常返态 $i$ 称为：
  * **正常返**（Positive Recurrent）：若 $\mu_i < \infty$
  * **零常返**（Null Recurrent）：若 $\mu_i = \infty$

**定理5.1** 对于常返态 $i$：
$$\lim_{n \to \infty} \frac{1}{n}\sum_{k=1}^{n} p_{ii}^{(k)} = \frac{1}{\mu_i}$$
若 $i$ 是周期为 $d$ 的常返态，则：
$$\lim_{n \to \infty} p_{ii}^{(nd)} = \frac{d}{\mu_i}$$

==== 5.2.2 状态分类的判别准则 ====

**定理5.2（状态分类总结）**

| 类型 | $\sum p_{ii}^{(n)}$ | $p_{ii}^{(n)} \to$ | 返回概率 | 平均返回时间 |
|------|---------------------|-------------------|----------|--------------|
| 非常返 | $< \infty$ | 0 | $< 1$ | $\infty$ |
| 零常返 | $= \infty$ | 0 | 1 | $\infty$ |
| 正常返 | $= \infty$ | $> 0$ | 1 | $< \infty$ |

**定理5.3** 有限状态的马尔可夫链不存在零常返态。

**证明**：若状态 $i$ 零常返，则 $\lim_{n \to \infty} p_{ii}^{(n)} = 0$。由常返性，$\sum_{j} p_{ij}^{(n)} = 1$ 对所有 $n$。但有限和与极限交换得 $0 = 1$，矛盾。

===== 5.3 周期性的深入讨论 =====

==== 5.3.1 循环子类 ====

**定理5.4** 设 $i$ 是周期为 $d$ 的常返态，则状态空间可分解为 $d$ 个互不相交的子集 $C_0, C_1, \ldots, C_{d-1}$，使得：
  * 若 $j \in C_r$，则 $\sum_{k \in C_{r+1}} p_{jk} = 1$（下标模 $d$）
  * $p_{ij}^{(n)} > 0$ 仅当 $j \in C_r$ 且 $n \equiv r \pmod{d}$

**例5.1** 简单随机游动：周期为2，偶数状态 $E = \{\ldots, -2, 0, 2, \ldots\}$ 和奇数状态 $O = \{\ldots, -1, 1, 3, \ldots\}$ 构成两个循环子类。

==== 5.3.2 非周期性的判别 ====

**定理5.5** 若存在 $n$ 使得 $p_{ii}^{(n)} > 0$ 且 $p_{ii}^{(n+1)} > 0$，则状态 $i$ 非周期。

**证明**：由定义，$d$ 整除 $n$ 和 $n+1$，故 $d = 1$。

**推论** 若 $p_{ii} > 0$，则状态 $i$ 非周期。

===== 5.4 不可约链的极限行为 =====

==== 5.4.1 遍历定理 ====

**定理5.6（遍历定理）** 设 $\{X_n\}$ 是不可约遍历马尔可夫链（正常返且非周期），则：

(1) 极限 $\pi_j = \lim_{n \to \infty} p_{ij}^{(n)}$ 存在且与 $i$ 无关

(2) $\boldsymbol{\pi} = (\pi_j)$ 是唯一的平稳分布，满足：
$$\pi_j > 0, \quad \sum_j \pi_j = 1, \quad \pi_j = \sum_i \pi_i p_{ij}$$

(3) $\pi_j = \frac{1}{\mu_j}$

==== 5.4.2 周期链的极限 ====

**定理5.7** 设 $\{X_n\}$ 是不可约正常返周期为 $d$ 的马尔可夫链，则：
$$\lim_{n \to \infty} p_{ij}^{(nd+r)} = d \cdot \pi_j$$
当 $n \not\equiv r \pmod{d}$ 时，$p_{ij}^{(n)} = 0$（若 $j$ 在 $i$ 的 $r$ 步循环子类中）。

===== 5.5 平稳分布的存在性与唯一性 =====

==== 5.5.1 存在性定理 ====

**定理5.8** 不可约马尔可夫链存在平稳分布当且仅当它是正常返的。

==== 5.5.2 唯一性定理 ====

**定理5.9** 不可约正常返马尔可夫链的平稳分布唯一。

==== 5.5.3 有限链的平稳分布 ====

**定理5.10** 有限状态的不可约马尔可夫链必存在唯一的平稳分布。

===== 5.6 可逆马尔可夫链 =====

**定义5.3（细致平衡）** 分布 $\boldsymbol{\pi}$ 满足**细致平衡条件**，如果对任意 $i, j$：
$$\pi_i p_{ij} = \pi_j p_{ji}$$

**定理5.11** 若 $\boldsymbol{\pi}$ 满足细致平衡条件，则 $\boldsymbol{\pi}$ 是平稳分布。

**证明**：对 $j$ 求和：
$$\sum_i \pi_i p_{ij} = \sum_i \pi_j p_{ji} = \pi_j \sum_i p_{ji} = \pi_j$$

**定义5.4（可逆链）** 若马尔可夫链以平稳分布为初始分布时，对任意 $n$ 和状态序列：
$$P(X_0 = i_0, X_1 = i_1, \ldots, X_n = i_n) = P(X_0 = i_n, X_1 = i_{n-1}, \ldots, X_n = i_0)$$
则称其为**可逆**的。

**定理5.12** 不可约马尔可夫链可逆当且仅当细致平衡条件成立。

**例5.2（生灭链）** 状态空间 $S = \{0, 1, 2, \ldots\}$，转移：
$$p_{i,i+1} = p_i, \quad p_{i,i-1} = q_i = 1-p_i \text{（}i \geq 1\text{）}, \quad p_{01} = 1$$

设平稳分布存在，由细致平衡：
$$\pi_i p_i = \pi_{i+1} q_{i+1}$$

因此：
$$\pi_i = \pi_0 \prod_{k=0}^{i-1} \frac{p_k}{q_{k+1}}$$

归一化条件 $\sum \pi_i = 1$ 确定 $\pi_0$。

===== 5.7 收敛速率与谱理论 =====

==== 5.7.1 收敛速率 ====

对于遍历链，$p_{ij}^{(n)} \to \pi_j$ 的收敛速率由转移矩阵的**谱隙**决定。

**定义5.5（全变差距离）** 两个概率分布 $\mu$ 和 $\nu$ 的**全变差距离**：
$$\|\mu - \nu\|_{TV} = \frac{1}{2}\sum_i |\mu_i - \nu_i|$$

**定理5.13** 对于遍历链，存在常数 $C > 0$ 和 $\rho \in (0, 1)$ 使得：
$$\|\boldsymbol{\pi}^{(n)} - \boldsymbol{\pi}\|_{TV} \leq C \rho^n$$

==== 5.7.2 混合时间 ====

**定义5.6（混合时间）** 
$$\tau_{mix}(\epsilon) = \min\{n: \max_i \|\mathbf{P}_i^{(n)} - \boldsymbol{\pi}\|_{TV} \leq \epsilon\}$$
通常取 $\epsilon = 1/4$，记为 $\tau_{mix}$。

===== 5.8 马尔可夫链的大数定律 =====

**定理5.14（马尔可夫链的强大数定律）** 设 $\{X_n\}$ 是不可约正常返马尔可夫链，平稳分布为 $\boldsymbol{\pi}$，$f$ 是状态空间上的函数且 $\sum_i |f(i)|\pi_i < \infty$，则：
$$\frac{1}{n}\sum_{k=0}^{n-1} f(X_k) \to \sum_i f(i)\pi_i \quad \text{a.s.}$$

这一定理说明时间平均等于空间平均（遍历性）。

===== 5.9 本章例题详解 =====

**例题1** 设转移矩阵：
$$\mathbf{P} = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$$

分析状态分类和极限行为。

**解**：

这是一个循环链，$0 \to 1 \to 2 \to 0$，周期为3。

$\mathbf{P}^3 = \mathbf{I}$，故对所有 $i$，$\mu_i = 3$，正常返。

平稳分布：由对称性，$\pi = (1/3, 1/3, 1/3)$。

极限：$p_{ii}^{(3n)} = 1 \to 1 = 3 \times (1/3) = d\pi_i$，符合定理5.7。

**例题2** Ehrenfest模型：$N$ 个分子在两个容器间转移。

证明：(1) 链不可约 (2) 平稳分布为二项分布 $B(N, 1/2)$。

**解**：

(1) 从任意状态 $i$，通过连续转移可达到任意状态 $j$，故不可约。

(2) 设 $\pi_i = \binom{N}{i} 2^{-N}$，验证细致平衡：
$$\pi_i p_{i,i+1} = \binom{N}{i} 2^{-N} \cdot \frac{N-i}{N} = \frac{N!}{i!(N-i)!} \cdot \frac{N-i}{N} \cdot 2^{-N}$$
$$\pi_{i+1} p_{i+1,i} = \binom{N}{i+1} 2^{-N} \cdot \frac{i+1}{N} = \frac{N!}{(i+1)!(N-i-1)!} \cdot \frac{i+1}{N} \cdot 2^{-N}$$

两式相等，故细致平衡成立，$\boldsymbol{\pi}$ 是平稳分布。

**例题3** 证明：若马尔可夫链有多个常返类，则平稳分布不唯一。

**证明**：设 $C_1$ 和 $C_2$ 是两个不同的常返类，分别有平稳分布 $\boldsymbol{\pi}^{(1)}$ 和 $\boldsymbol{\pi}^{(2)}$（在各自类上支撑）。则对任意 $\alpha \in [0, 1]$，$\alpha \boldsymbol{\pi}^{(1)} + (1-\alpha) \boldsymbol{\pi}^{(2)}$ 都是平稳分布。

===== 5.10 本章习题 =====

**习题5.1** 设 $\mathbf{P} = \begin{pmatrix} 1/2 & 1/2 \\ 1 & 0 \end{pmatrix}$。

(1) 判断各状态的周期性
(2) 求平稳分布
(3) 求 $\lim_{n \to \infty} \frac{1}{n}\sum_{k=1}^n \mathbf{P}^k$

**习题5.2** 设 $\{X_n\}$ 是状态空间 $\mathbb{Z}$ 上的随机游动，$p_{i,i+1} = p$，$p_{i,i-1} = q = 1-p$。

(1) 证明：当 $p \neq q$ 时，链非常返
(2) 当 $p = q = 1/2$ 时，证明链零常返

**习题5.3** 设 $\mathbf{P} = \begin{pmatrix} 0 & 1/2 & 1/2 \\ 1/2 & 0 & 1/2 \\ 1/2 & 1/2 & 0 \end{pmatrix}$。

(1) 验证链可逆
(2) 求平稳分布
(3) 计算混合时间的上界

**习题5.4** 设生灭链，$p_i = p$，$q_i = q = 1-p$ 对所有 $i \geq 1$，$p_0 = 1$。

(1) 求链正常返的条件
(2) 在正常返条件下求平稳分布

**习题5.5** 证明：若 $\boldsymbol{\pi}$ 是平稳分布，$\boldsymbol{\pi}^{(0)} = \boldsymbol{\pi}$，则对所有 $n$，$\boldsymbol{\pi}^{(n)} = \boldsymbol{\pi}$。

**习题5.6** 设马尔可夫链的状态空间为 $\{0, 1, 2, \ldots\}$，转移概率 $p_{0i} = p_i$（$\sum p_i = 1$），$p_{i,i-1} = 1$ 对 $i \geq 1$。

(1) 证明链不可约
(2) 求链正常返的条件
(3) 在正常返条件下求平稳分布

**习题5.7** 设 $\mathbf{P}$ 是双随机矩阵，证明均匀分布是平稳分布。进一步，若 $\mathbf{P}$ 还是对称的，证明链可逆。

**习题5.8** 设 $\{X_n\}$ 是遍历马尔可夫链，$f$ 是有界函数。定义 $S_n = \sum_{k=0}^{n-1} f(X_k)$。证明：
$$\frac{S_n - n\bar{f}}{\sqrt{n}} \stackrel{d}{\to} N(0, \sigma^2)$$
其中 $\bar{f} = \sum_i f(i)\pi_i$，求 $\sigma^2$ 的表达式。

----

**上一章**：[[第四章_离散时间马尔可夫链]] | **下一章**：[[第六章_连续时间马尔可夫链]]