马尔可夫链的收敛速率
我们首先回顾马尔可夫链的平稳分布和收敛定理。若一个不可约、非周期的马尔可夫链存在平稳分布 \(\pi\)，则无论初始分布如何，链在时间趋于无穷时都会收敛到 \(\pi\)，即：
\[\lim_{n \to \infty} P^n(x, y) = \pi(y), \quad \forall x, y \in \mathcal{X}. \]
但收敛定理并未说明收敛的速度有多快。收敛速率研究的是链以多快的速度接近平稳分布，通常通过衡量分布间的距离（如总变差距离）随时间衰减的行为来刻画。
步骤1：收敛速率的度量工具——总变差距离
总变差距离（Total Variation Distance）是衡量两个概率分布 \(\mu\) 和 \(\nu\) 差异的常用指标：
\[\|\mu - \nu\|_{\mathrm{TV}} = \sup_{A \subseteq \mathcal{X}} |\mu(A) - \nu(A)|. \]
对于可数状态空间，等价定义为：
\[\|\mu - \nu\|_{\mathrm{TV}} = \frac{1}{2} \sum_{x \in \mathcal{X}} |\mu(x) - \nu(x)|. \]
在马尔可夫链中，我们关心的是第 \(n\) 步分布 \(P^n(x, \cdot)\) 与平稳分布 \(\pi\) 的总变差距离如何随 \(n\) 衰减。
步骤2：混合时间与收敛速率的定量描述
收敛速率常通过混合时间（Mixing Time）来量化。混合时间定义为总变差距离降至某个阈值 \(\varepsilon\) 以下所需的最小步数：
\[t_{\mathrm{mix}}(\varepsilon) = \min \left\{ n : \max_{x \in \mathcal{X}} \|P^n(x, \cdot) - \pi\|_{\mathrm{TV}} \leq \varepsilon \right\}. \]
通常特别关注 \(t_{\mathrm{mix}}(1/4)\)，因为不同 \(\varepsilon\) 对应的混合时间可通过不等式相互转换。
步骤3：收敛速率的影响因素
收敛速率取决于链的结构性质，例如：
- 谱间隙（Spectral Gap）：若链可逆（满足细致平衡条件），其转移矩阵的特征值满足 \(1 = \lambda_1 > \lambda_2 \geq \cdots \geq \lambda_{|\mathcal{X}|} > -1\)。谱间隙定义为 \(\gamma_* = 1 - \max\{|\lambda_2|, |\lambda_{|\mathcal{X}|}|\}\)。谱间隙越大，收敛越快，总变差距离以指数速度衰减：
\[\|P^n(x, \cdot) - \pi\|_{\mathrm{TV}} \leq C \cdot (1 - \gamma_*)^n. \]
- ** conductance**：对于状态空间的划分，若链在任意子集与补集之间转移的概率较大，则收敛较快。这一性质可通过等周不等式与谱间隙关联。
步骤4：收敛速率的分析方法
常用技术包括：
- 耦合方法：构造两个分别从不同初始状态出发的链，使其在某个随机时刻后保持一致。耦合时间期望的上界直接给出混合时间的估计。
- 谱方法：通过分析转移算子的特征值界限谱间隙，进而控制收敛速率。
- Lyapunov函数方法：对于非有限状态空间，通过构造能量函数证明几何遍历性（指数收敛）。
步骤5：应用与意义
收敛速率分析在以下领域至关重要：
- MCMC算法评估：确保采样效率，如Gibbs采样、Metropolis-Hastings算法的混合时间决定了计算成本。
- 随机模型的动态分析：如排队网络、遗传算法中的随机过程收敛速度影响系统稳定性。
- 理论计算机科学：在近似计数、随机游走算法中，混合时间直接关联算法复杂度。
通过以上步骤，我们逐步理解了马尔可夫链收敛速率的核心概念、度量工具、影响因素及分析方法。这一理论将抽象的收敛性转化为可计算的量化指标，为实际应用提供了重要指导。