马尔可夫链的耦合方法
字数 783 2025-11-18 18:03:10

马尔可夫链的耦合方法

耦合方法是一种分析马尔可夫链收敛性的概率技术，其核心思想是构造两个或多个具有相同转移概率但初始状态不同的马尔可夫链，使其在某个随机时刻后保持相同状态。下面逐步展开说明：

  1. 基本定义
    • 设两个马尔可夫链 \(\{X_n\}\) 和 \(\{Y_n\}\) 在相同状态空间 \(S\) 上具有相同的转移概率矩阵 \(P\)。
    • 耦合指构造一个新的随机过程 \(\{(X_n, Y_n)\}\)，使得：
  • 每个分量 \(X_n\) 和 \(Y_n\) 单独看均满足原马尔可夫链的转移规则；
  • 存在某个随机时间 \(T\)（耦合时间），使得对所有 \(n \geq T\)，有 \(X_n = Y_n\)。

  1. 耦合时间的意义

    • 耦合时间 \(T = \inf\{n \geq 0: X_n = Y_n\}\) 是第一个使两个链相等的时刻。
    • 通过分析 \(T\) 的分布，可量化两个链从不同初值收敛到同一分布的速度。

  2. 收敛性分析

    • 对任意初始状态 \(i,j\)，总变差距离满足：

\[ \|P^n(i, \cdot) - P^n(j, \cdot)\|_{\text{TV}} \leq \mathbb{P}(T > n) \]

  • 若 \(\mathbb{P}(T < \infty) = 1\)，则链是遍历的，且平稳分布唯一。
  1. 最大耦合构造
    • 最优耦合使两链在每一步以最大概率相等，具体为：
  • 以概率 \(\min\{P(i,k), P(j,k)\}\) 同时转移到同一状态 \(k\)；
    • 否则按特定方式分别转移，使边际分布保持不变。

  1. 应用场景

    • 估计马尔可夫链混合时间；
    • 证明中心极限定理和遍历定理；
    • 研究随机过程的渐近独立性。

  2. 扩展方向

    • 可推广到连续时间马尔可夫链或非时齐链；
    • 与谱间隙、Wasserstein距离等工具结合，提供更紧的收敛界。
马尔可夫链的耦合方法 耦合方法是一种分析马尔可夫链收敛性的概率技术，其核心思想是构造两个或多个具有相同转移概率但初始状态不同的马尔可夫链，使其在某个随机时刻后保持相同状态。下面逐步展开说明： 基本定义 设两个马尔可夫链 \(\{X_ n\}\) 和 \(\{Y_ n\}\) 在相同状态空间 \(S\) 上具有相同的转移概率矩阵 \(P\)。 耦合指构造一个新的随机过程 \(\{(X_ n, Y_ n)\}\)，使得： 每个分量 \(X_ n\) 和 \(Y_ n\) 单独看均满足原马尔可夫链的转移规则； 存在某个随机时间 \(T\)（耦合时间），使得对所有 \(n \geq T\)，有 \(X_ n = Y_ n\)。 耦合时间的意义 耦合时间 \(T = \inf\{n \geq 0: X_ n = Y_ n\}\) 是第一个使两个链相等的时刻。 通过分析 \(T\) 的分布，可量化两个链从不同初值收敛到同一分布的速度。 收敛性分析 对任意初始状态 \(i,j\)，总变差距离满足： \[ \|P^n(i, \cdot) - P^n(j, \cdot)\|_ {\text{TV}} \leq \mathbb{P}(T > n) \] 若 \(\mathbb{P}(T < \infty) = 1\)，则链是遍历的，且平稳分布唯一。 最大耦合构造 最优耦合使两链在每一步以最大概率相等，具体为： 以概率 \(\min\{P(i,k), P(j,k)\}\) 同时转移到同一状态 \(k\)； 否则按特定方式分别转移，使边际分布保持不变。 应用场景 估计马尔可夫链混合时间； 证明中心极限定理和遍历定理； 研究随机过程的渐近独立性。 扩展方向 可推广到连续时间马尔可夫链或非时齐链； 与谱间隙、Wasserstein距离等工具结合，提供更紧的收敛界。