马尔可夫链的谱隙与收敛速度
接下来，我将为你系统性地讲解这个概念。我们将从最基础的相关概念出发，逐步深入，最终清晰地理解什么是马尔可夫链的“谱隙”（Spectral Gap），以及它如何定量刻画马尔可夫链收敛到平稳分布的速度。
步骤 1：前置知识回顾与问题提出
首先，我们需要明确几个已经讲过的背景概念，它们是理解谱隙的基石：
- 马尔可夫链：一个具有“无记忆性”的随机过程，其未来状态的条件概率分布只依赖于当前状态。
- 平稳分布：一个概率分布 π，如果链从 π 开始，那么在任意时刻的分布都保持为 π。对于满足一定条件（如不可约、非周期）的链，无论从哪个初始状态出发，其长期分布都会趋近于这个唯一的平稳分布 π。
- 收敛速率：这是你已学过词条的核心。我们关心的是，链的分布 \(P^n(x, ·)\) （从初始状态 \(x\) 出发，经过 \(n\) 步后的分布）以多快的速度“接近”平稳分布 π。接近的程度需要用某种距离来衡量，例如总变差距离。
核心问题：如何用一个数值来量化这种收敛速度？这个数值就是“谱隙”。
步骤 2：将马尔可夫链视为一个线性算子
这是理解谱隙的关键思维跃迁。我们暂时离开概率视角，进入泛函分析的视角。
- 一个（状态空间有限的、时间离散的）马尔可夫链由其转移概率矩阵 \(P\) 完全描述。
- 矩阵 \(P\) 不仅可以作用在概率分布向量上（右乘：\(\mu_{n+1} = \mu_n P\)），也可以作用在定义在状态空间上的函数（或向量）\(f\) 上（左乘）。
- 定义算子 \(P\) 对函数 \(f\) 的作用为：\((Pf)(x) = \sum_y P(x， y) f(y)\)。可以理解为函数 \(f\) 在下一步的期望值。
- 在这个视角下，平稳分布 π 对应于算子 \(P\) 的一个特征值为 1 的右特征向量（因为 \(πP = π\)）。同时，常值函数 1（所有状态取值为1的函数）是特征值 1 对应的左特征向量（因为 \(P1 = 1\)）。
步骤 3：在适当的空间里考察算子 P
为了使分析更清晰，我们需要将算子 \(P\) 放在一个合适的“舞台”上。这个舞台就是 \(L^2(π)\) 空间。
- \(L^2(π)\) 空间：由所有满足 \(\mathbb{E}_\pi[f^2] < \infty\) 的函数 \(f\) 构成的空间。这里的内积定义为：
\[ \langle f, g \rangle_\pi = \sum_x f(x) g(x) \pi(x) \]
即关于平稳分布 π 的加权内积。相应的范数为 \(\|f\|_\pi = \sqrt{\langle f, f \rangle_\pi}\)。
- 为什么选择这个空间？ 在这个内积下，如果链是可逆的（即满足细致平衡条件 \(\pi(x)P(x， y) = \pi(y)P(y, x)\)），那么转移算子 \(P\) 是 \(L^2(π)\) 空间上的一个自伴算子（相当于实对称矩阵）。这意味着它的所有特征值都是实数，并且特征函数可以构成一组正交基。这极大简化了分析。
步骤 4：算子 P 的谱（特征值）
对于一个在 \(L^2(π)\) 上可逆的马尔可夫链，其转移算子 \(P\) 具有以下谱性质：
- 最大特征值：\(\lambda_1 = 1\)，对应的特征函数是常值函数 \(f_1(x) \equiv 1\)。
- 其他特征值：由于 \(P\) 是随机矩阵，其所有特征值都落在复平面的单位圆内。对于可逆链，这些特征值都是实数，因此它们满足：
\[ 1 = \lambda_1 \ge \lambda_2 \ge \lambda_3 \ge \dots \ge \lambda_N \ge -1 \]
（假设状态空间大小为 \(N\)）。
步骤 5：定义谱隙
谱隙 正是基于上述谱结构定义的。它有两种常见但等价的定义方式：
- 绝对谱隙：定义为第二大的特征值的绝对值与1的差距。
\[ \gamma_* = 1 - \max\{ |\lambda_2|， |\lambda_N| \} \]
它衡量了除1以外的所有特征值距离单位圆边界有多远。
- （有时特指的）谱隙：在可逆且非周期链中，所有特征值非负且小于等于1，此时第二大的特征值 \(\lambda_2\) 是关键。我们定义谱隙为：
\[ \gamma = 1 - \lambda_2 \]
**这就是最常用、最核心的定义。** 它衡量了第二大特征值与最大特征值（1）之间的“间隙”。
关键理解：\(\lambda_2\) 是最慢衰减的模态所对应的速率。任何初始分布与平稳分布的偏差，都可以投影到特征函数上。投影在特征值 \(\lambda_2\) 对应的模态上的部分，其衰减速度由 \(\lambda_2^n\) 控制。因此，\(\lambda_2\) 越接近1，衰减越慢，收敛越慢；\(\lambda_2\) 离1越远（即谱隙 \(\gamma\) 越大），衰减越快，收敛越快。
步骤 6：谱隙如何控制收敛速度——一个精确的联系
通过谱理论，我们可以建立谱隙与总变差距离收敛速度之间的直接不等式关系。
对于一个可逆、不可约、非周期的有限马尔可夫链，从初始分布 \(\mu\) 出发，经过 \(n\) 步后，有：
\[\|\mu P^n - \pi\|_{\text{TV}} \le \frac{1}{2} \sqrt{\frac{1 - \pi_{\min}}{\pi_{\min}}} \cdot (1 - \gamma)^n = \frac{1}{2} \sqrt{\frac{1 - \pi_{\min}}{\pi_{\min}}} \cdot \lambda_2^n \]
其中 \(\pi_{\min}\) 是平稳分布中最小的概率，\(\|·\|_{\text{TV}}\) 是总变差距离。
解读：
- 收敛速度在数量级上由 \(\lambda_2^n\) 或 \((1-\gamma)^n\) 控制。这是指数级的收敛。
- 谱隙 \(\gamma\) 直接出现在指数衰减率中：\(\gamma\) 越大，\((1-\gamma)\) 越小，指数衰减越快。
- 前面的常数项与初始分布和平稳分布的具体结构有关，但决定收敛“快慢感”的核心是指数部分 \(\lambda_2^n\)。
步骤 7：混和时间的定量描述
你已学过“马尔可夫链的混合时间”，谱隙为其提供了最经典的上界。
松弛时间 定义为：
\[t_{\text{rel}} = \frac{1}{\gamma} \]
它反映了链“忘记”初始状态所需时间的尺度。
混合时间 \(t_{\text{mix}}(\epsilon)\) （达到与平稳分布总变差距离小于 \(\epsilon\) 所需的最少步数）满足：
\[t_{\text{mix}}(\epsilon) \le t_{\text{rel}} \cdot \log\left(\frac{1}{\epsilon \pi_{\min}}\right) \]
这清晰地表明：谱隙越大（\(\gamma\) 越大），松弛时间越短，混合时间也越短，链收敛得越快。
步骤 8：总结与应用意义
现在，让我们把整个逻辑串联起来：
- 目标：量化马尔可夫链收敛到平稳分布的速度。
- 方法转换：将概率问题（转移矩阵 \(P\) ）转化为线性算子分析问题。
- 舞台搭建：在 \(L^2(π)\) 空间（关于平稳分布加权的空间）中研究算子 \(P\)，对于可逆链，\(P\) 是自伴的。
- 谱分析：算子 \(P\) 的特征值 \(1=\lambda_1 \ge \lambda_2 \ge ...\) 控制了不同方向（模态）的衰减速度。
- 定义谱隙：\(\gamma = 1 - \lambda_2\)。它度量了最慢衰减模态的衰减速率与1的差距，是收敛速度的内在、根本性的度量。
- 定量控制：谱隙通过不等式直接控制了总变差距离的指数衰减速率和混合时间。大的谱隙意味着快的指数收敛。
应用意义：在马尔可夫链蒙特卡洛方法中，我们通过构造马尔可夫链来抽样复杂的平稳分布。计算或估计这个链的谱隙，是理论上分析和比较不同MCMC算法效率（需要多少步才能得到接近独立的样本）的核心工具。谱隙是连接马尔可夫链的代数/分析性质与其概率统计行为（收敛速率）的一座关键桥梁。