马尔可夫链的谱间隙
字数 1247 2025-11-14 05:18:55

马尔可夫链的谱间隙

  1. 基本定义
    马尔可夫链的谱间隙是刻画其收敛速度的重要指标。对于一个具有转移矩阵 \(P\) 的不可约、非周期且可逆的马尔可夫链，其生成算子（或转移矩阵）在 \(L^2\) 空间中的特征值按降序排列为：

\[ 1 = \lambda_1 > \lambda_2 \geq \lambda_3 \geq \cdots \geq \lambda_n \geq -1. \]

谱间隙定义为最大特征值与第二大特征值之间的差值：

\[ \gamma = 1 - \lambda_2. \]

若链不可约且非周期，则 \(\lambda_2 < 1\)，此时谱间隙 \(\gamma > 0\)。

  1. 谱间隙与收敛速度的关系
    谱间隙直接关联到马尔可夫链的混合时间（即接近平稳分布所需的时间）。对于任意初始分布 \(\mu_0\)，经过 \(t\) 步转移后的分布 \(\mu_t\) 与平稳分布 \(\pi\) 的总变差距离满足：

\[ \|\mu_t - \pi\|_{\mathrm{TV}} \leq C \cdot (1 - \gamma)^t, \]

其中 \(C\) 为与初始分布相关的常数。这表明谱间隙 \(\gamma\) 越大，链的收敛速度越快。

  1. 谱间隙的计算方法
    谱间隙可通过以下途径计算或估计：
    • 特征值分解：直接计算转移矩阵 \(P\) 的特征值，但仅适用于小型状态空间。
    • 变分公式：对于可逆马尔可夫链，谱间隙满足：

\[ \gamma = \inf\left\{ \frac{\mathcal{E}(f, f)}{\mathrm{Var}_\pi(f)} : f \neq \text{常数} \right\}, \]

其中 \(\mathcal{E}(f, f) = \frac{1}{2} \sum_{x,y} (f(x) - f(y))^2 \pi(x) P(x,y)\) 是狄利克雷形式，\(\mathrm{Var}_\pi(f)\) 是方差。

  • 几何工具：如康托洛维奇-达林（Kantorovich-Dobrushin）不等式或路径方法。

  1. 应用与实例

    • 随机游走：在 \(n\) 个顶点的完全图上，简单随机游走的谱间隙为 \(\gamma = 1 - \frac{1}{n-1}\)，接近 1，因此混合极快。
    • 马尔可夫链蒙特卡洛（MCMC）：谱间隙用于评估吉布斯采样或Metropolis-Hastings算法的效率。若谱间隙过小，链可能陷入“局部状态”，需通过调整提案分布优化。

  2. 扩展概念

    • 松弛时间：定义为 \(\tau_{\mathrm{rel}} = 1 / \gamma\)，直接表征收敛到平稳分布的速率。
    • 对数索博列夫不等式：比谱间隙更精细的工具，可处理非可逆链或高维问题。
    • 谱轮廓曲线：针对非可逆链的推广，通过分析生成算子的伪谱得到收敛界。
马尔可夫链的谱间隙 基本定义 马尔可夫链的谱间隙是刻画其收敛速度的重要指标。对于一个具有转移矩阵 \( P \) 的不可约、非周期且可逆的马尔可夫链，其生成算子（或转移矩阵）在 \( L^2 \) 空间中的特征值按降序排列为： \[ 1 = \lambda_ 1 > \lambda_ 2 \geq \lambda_ 3 \geq \cdots \geq \lambda_ n \geq -1. \] 谱间隙定义为最大特征值与第二大特征值之间的差值： \[ \gamma = 1 - \lambda_ 2. \] 若链不可约且非周期，则 \( \lambda_ 2 < 1 \)，此时谱间隙 \( \gamma > 0 \)。 谱间隙与收敛速度的关系 谱间隙直接关联到马尔可夫链的混合时间（即接近平稳分布所需的时间）。对于任意初始分布 \( \mu_ 0 \)，经过 \( t \) 步转移后的分布 \( \mu_ t \) 与平稳分布 \( \pi \) 的总变差距离满足： \[ \|\mu_ t - \pi\|_ {\mathrm{TV}} \leq C \cdot (1 - \gamma)^t, \] 其中 \( C \) 为与初始分布相关的常数。这表明谱间隙 \( \gamma \) 越大，链的收敛速度越快。 谱间隙的计算方法 谱间隙可通过以下途径计算或估计： 特征值分解 ：直接计算转移矩阵 \( P \) 的特征值，但仅适用于小型状态空间。 变分公式 ：对于可逆马尔可夫链，谱间隙满足： \[ \gamma = \inf\left\{ \frac{\mathcal{E}(f, f)}{\mathrm{Var} \pi(f)} : f \neq \text{常数} \right\}, \] 其中 \( \mathcal{E}(f, f) = \frac{1}{2} \sum {x,y} (f(x) - f(y))^2 \pi(x) P(x,y) \) 是狄利克雷形式，\( \mathrm{Var}_ \pi(f) \) 是方差。 几何工具 ：如康托洛维奇-达林（Kantorovich-Dobrushin）不等式或路径方法。 应用与实例 随机游走 ：在 \( n \) 个顶点的完全图上，简单随机游走的谱间隙为 \( \gamma = 1 - \frac{1}{n-1} \)，接近 1，因此混合极快。 马尔可夫链蒙特卡洛（MCMC） ：谱间隙用于评估吉布斯采样或Metropolis-Hastings算法的效率。若谱间隙过小，链可能陷入“局部状态”，需通过调整提案分布优化。 扩展概念 松弛时间 ：定义为 \( \tau_ {\mathrm{rel}} = 1 / \gamma \)，直接表征收敛到平稳分布的速率。 对数索博列夫不等式 ：比谱间隙更精细的工具，可处理非可逆链或高维问题。 谱轮廓曲线 ：针对非可逆链的推广，通过分析生成算子的伪谱得到收敛界。