马尔可夫链的收敛速率 基本定义与背景 马尔可夫链的收敛速率描述了马尔可夫链从初始分布收敛到平稳分布的速度。若马尔可夫链满足不可约性、非周期性和正常返性（即遍历性），则其分布会随时间收敛到唯一的平稳分布。收敛速率通过衡量第 \( n \) 步转移概率与平稳分布之间的差异来量化，常用工具包括 总变差距离 和 谱间隙 。 总变差距离与收敛度量 定义第 \( n \) 步分布 \( P^n(x, \cdot) \) 与平稳分布 \( \pi \) 的总变差距离为： \[ d_ {\mathrm{TV}}(n) = \sup_ {x \in \mathcal{X}} \| P^n(x, \cdot) - \pi \| {\mathrm{TV}} = \sup {x \in \mathcal{X}} \sup_ {A \subseteq \mathcal{X}} |P^n(x, A) - \pi(A)|. \] 收敛速率研究 \( d_ {\mathrm{TV}}(n) \) 随 \( n \) 增大而衰减的规律，例如指数衰减 \( d_ {\mathrm{TV}}(n) \leq C e^{-\gamma n} \)。 谱间隙与指数收敛 若马尔可夫链的转移矩阵 \( P \) 在 \( L^2(\pi) \) 空间中是自伴的，其特征值满足 \( 1 = \lambda_ 1 > \lambda_ 2 \geq \cdots \geq \lambda_ {|\mathcal{X}|} > -1 \)。定义 谱间隙 为 \( \gamma_* = 1 - \max\{ |\lambda_ 2|, |\lambda_ {|\mathcal{X}|}| \} \)。 此时，收敛速率满足： \[ d_ {\mathrm{TV}}(n) \leq \frac{1}{2} \| P^n(x, \cdot) - \pi \| {L^2(\pi)} \leq \frac{1}{2} \sqrt{\frac{1}{\pi {\min}}} (1 - \gamma_ )^n, \] 其中 \( \pi_ {\min} = \min_ x \pi(x) \)。谱间隙 \( \gamma_ \) 越大，收敛越快。 混合时间与应用 混合时间 \( t_ {\mathrm{mix}}(\varepsilon) \) 定义为使 \( d_ {\mathrm{TV}}(n) \leq \varepsilon \) 的最小 \( n \)。当 \( \varepsilon = 1/4 \) 时，常记 \( t_ {\mathrm{mix}} = t_ {\mathrm{mix}}(1/4) \)。混合时间与谱间隙满足关系： \[ t_ {\mathrm{mix}} \leq \frac{1}{\gamma_* } \log \left( \frac{1}{\varepsilon \pi_ {\min}} \right). \] 该结果在马尔可夫链蒙特卡洛（MCMC）方法中至关重要，用于评估采样效率。 非可逆链与广义谱间隙 对于非可逆链（转移矩阵非对称），需通过 伪谱间隙 或 弛豫时间 分析收敛性。定义弛豫时间为 \( t_ {\mathrm{rel}} = 1 / \gamma_* \)，此时收敛速率满足： \[ d_ {\mathrm{TV}}(n) \leq \left( \frac{1}{\pi_ {\min}} \right) e^{-n / t_ {\mathrm{rel}}}. \] 此方法扩展了谱理论的应用范围，适用于更复杂的链结构。 下界与最优性 收敛速率的分析常结合 耦合方法 或** conductance** 技术。例如，通过 conductance \( \Phi \) 定义： \[ \Phi = \min_ {S: \pi(S) \leq 1/2} \frac{\sum_ {x \in S, y \notin S} \pi(x) P(x, y)}{\pi(S)}, \] 可证 \( \gamma_* \geq \Phi^2 / 2 \)（Cheeger不等式），从而建立收敛速率的下界，确保估计的紧性。