本章深入研究马尔可夫链状态空间的精细结构，系统讨论状态的分类方法、极限行为以及平稳分布的理论。这些内容构成了马尔可夫链理论的核心，也是应用马尔可夫链解决实际问题的基础。
定义5.1（平均返回时间） 对于常返态 $i$，定义平均返回时间： $$\mu_i = E[T_i | X_0 = i] = \sum_{n=1}^{\infty} n f_{ii}^{(n)}$$
定义5.2（正常返与零常返） 常返态 $i$ 称为：
定理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（状态分类总结）
| 类型 | $\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.4 设 $i$ 是周期为 $d$ 的常返态，则状态空间可分解为 $d$ 个互不相交的子集 $C_0, C_1, \ldots, C_{d-1}$，使得：
例5.1 简单随机游动：周期为2，偶数状态 $E = \{\ldots, -2, 0, 2, \ldots\}$ 和奇数状态 $O = \{\ldots, -1, 1, 3, \ldots\}$ 构成两个循环子类。
定理5.5 若存在 $n$ 使得 $p_{ii}^{(n)} > 0$ 且 $p_{ii}^{(n+1)} > 0$，则状态 $i$ 非周期。
证明：由定义，$d$ 整除 $n$ 和 $n+1$，故 $d = 1$。
推论 若 $p_{ii} > 0$，则状态 $i$ 非周期。
定理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.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.8 不可约马尔可夫链存在平稳分布当且仅当它是正常返的。
定理5.9 不可约正常返马尔可夫链的平稳分布唯一。
定理5.10 有限状态的不可约马尔可夫链必存在唯一的平稳分布。
定义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$。
对于遍历链，$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.6（混合时间） $$\tau_{mix}(\epsilon) = \min\{n: \max_i \|\mathbf{P}_i^{(n)} - \boldsymbol{\pi}\|_{TV} \leq \epsilon\}$$ 通常取 $\epsilon = 1/4$，记为 $\tau_{mix}$。
定理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.}$$
这一定理说明时间平均等于空间平均（遍历性）。
例题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.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$ 的表达式。
上一章：第四章_离散时间马尔可夫链 | 下一章：第六章_连续时间马尔可夫链