马尔可夫链的耦合方法（续）
字数 4124 2025-12-20 22:57:28

马尔可夫链的耦合方法（续）

在先前对“马尔可夫链的耦合方法”的基本介绍中，我们已经了解了耦合的核心思想是构造两个（或多个）马尔可夫链的联合过程，使其各自的边际演化遵循给定的转移概率。现在，我们深入探讨其两大核心应用：估计收敛速度与证明分布的极限唯一性。我们将从一个具体例子出发，逐步展示其技术细节。

第一步：回顾目标与设定
假设我们有一个在有限状态空间 \(S\) 上的、不可约且非周期的马尔可夫链 \((X_n)\)，其转移矩阵为 \(P\)。该链具有唯一的平稳分布 \(\pi\)。我们关注其收敛速度，即如何量化 \(\| P(X_n = j) - \pi_j \|\) 随 \(n\) 衰减的快慢。耦合方法的核心是构造另一个从平稳分布 \(\pi\) 启动的链 \((Y_n)\)，即 \(Y_0 \sim \pi\)，并且 \((Y_n)\) 与 \((X_n)\) 具有相同的转移矩阵 \(P\)，但初始分布不同。

第二步：构造一个具体的耦合
我们的目标是在同一个概率空间上定义联合过程 \((X_n, Y_n)\)，使得：

  1. 每个分量单独看都是一个转移矩阵为 \(P\) 的马尔可夫链。
  2. \(X_0\) 服从任意初始分布 \(\mu\)（我们关心的起点），而 \(Y_0 \sim \pi\)（平稳分布）。
  3. 定义一个“耦合时间” \(T = \inf\{ n \geq 0: X_n = Y_n \}\)。我们希望构造的联合过程具有“粘性”（也叫“重合后同步”性质）：一旦在某个时刻 \(n\) 满足 \(X_n = Y_n\)，则在所有后续时刻 \(m > n\) 都强制 \(X_m = Y_m\)。这意味着两个链在相遇后永久地保持同步运动。

一个经典且实用的构造是最大耦合（Maximal Coupling），其思想是在每一步都尽可能让两个链“走到同一个状态”，以最大化它们在下一步就相遇的概率。不过，为了直观理解，我们可以描述一个更简单的、基于转移概率的构造思想：在每个时间步 \(n\)：

  • 如果 \(X_n \neq Y_n\)，我们可以让 \(X_{n+1}\) 和 \(Y_{n+1}\) 根据某个联合分布生成，这个联合分布的边际分布分别是 \(P(X_{n+1} | X_n)\) 和 \(P(Y_{n+1} | Y_n)\)，但可以存在相关性。一种常见策略是，以某个概率 \(\eta\) 尝试让它们跳到同一个状态（即“耦合尝试”），否则就独立地按照各自的转移概率跳跃。
  • 如果 \(X_n = Y_n\)，则从下一步开始，强制 \(X_{n+1} = Y_{n+1}\)，并且都按照转移概率 \(P\) 从该共同状态出发。

第三步：利用耦合时间控制分布距离
耦合不等式是分析的关键。对于任意状态 \(j\)，事件 \(\{X_n = j\}\) 可以分解为两部分：在时间 \(n\) 之前耦合已经发生（\(T \leq n\)）和尚未发生（\(T > n\)）。

\[\mathbb{P}(X_n = j) = \mathbb{P}(X_n = j, T \leq n) + \mathbb{P}(X_n = j, T > n) \]

由于在 \(T \leq n\) 时，由粘性性质可知 \(X_n = Y_n\)，所以 \(\mathbb{P}(X_n = j, T \leq n) = \mathbb{P}(Y_n = j, T \leq n)\)。而 \(Y_n\) 始终服从平稳分布 \(\pi\)。因此：

\[\mathbb{P}(X_n = j) - \pi_j = \mathbb{P}(X_n = j, T > n) - \mathbb{P}(Y_n = j, T > n) \]

对两边取绝对值并对所有状态 \(j\) 求和，我们得到全变差距离的上界：

\[\| \mu_n - \pi \|_{TV} := \frac{1}{2} \sum_{j} |\mathbb{P}(X_n = j) - \pi_j| \leq \mathbb{P}(T > n) \]

其中 \(\mu_n\) 是 \(X_n\) 的分布。这个不等式极为强大：它将两个分布的距离（一个涉及所有状态、难以直接计算的量）上界为耦合时间超过 \(n\) 的概率（一个单一事件的概率）。我们的任务转化为估计耦合时间 \(T\) 的尾部概率。

第四步：计算收敛速度的一个示例
假设链的状态空间是 \(\{1, 2\}\)，转移矩阵为：

\[P = \begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}, \quad 0 < a, b < 1 \]

其平稳分布为 \(\pi = (b/(a+b), a/(a+b))\)。现在构造一个简单的耦合：

  • 初始时，\(X_0\) 任意（例如总是从状态1启动），\(Y_0 \sim \pi\)。
  • 在每个时刻 \(n\)，如果 \(X_n \neq Y_n\)（即一个在1，另一个在2），则我们独立地投掷两枚硬币来决定它们的跳跃：
    • 对于链 \(X\)：以概率 \(1-a\) 留在当前状态，以概率 \(a\) 跳转。
    • 对于链 \(Y\)：以概率 \(1-b\) 留在当前状态，以概率 \(b\) 跳转。
  • 如果它们状态不同，要使它们下一步相遇，唯一的方式是：处在状态1的那个链（假设是 \(X\)）必须跳走（概率 \(a\)），而处在状态2的那个链（\(Y\)）必须跳走（概率 \(b\)）。如果它们都跳，则它们会在下一步交换位置，但仍然不相等。要使它们相等，我们需要其中一个链跳而另一个链不跳。计算这个概率：\(X\) 跳 (\(a\)) 且 \(Y\) 不跳 (\(1-b\)) 的概率是 \(a(1-b)\)，或者 \(X\) 不跳 (\(1-a\)) 且 \(Y\) 跳 (\(b\)) 的概率是 \((1-a)b\)。因此，在 \(X_n \neq Y_n\) 的条件下，下一步耦合成功（即 \(X_{n+1} = Y_{n+1}\)）的概率为 \(p_{couple} = a(1-b) + (1-a)b = a + b - 2ab\)。如果耦合不成功（概率 \(1 - p_{couple}\)），则它们可能保持原状或交换，但仍是 \(X_{n+1} \neq Y_{n+1}\)。
  • 一旦 \(X_n = Y_n\)，之后永久保持同步。

第五步：估计耦合时间的分布与收敛界
在这个耦合构造下，只要两个链尚未相同，每一步成功的概率是 \(p_{couple}\)。因此，从任意不同初始状态出发，耦合时间 \(T\) 服从一个几何分布（如果首次尝试就成功，则 \(T=1\)；否则需要多次尝试），其参数为 \(p_{couple}\)。更精确地，\(T\) 是以概率 \(p_{couple}\) 成功的几何随机变量，满足 \(\mathbb{P}(T > n) = (1 - p_{couple})^n\)。

由耦合不等式，我们得到：

\[\| \mu_n - \pi \|_{TV} \leq \mathbb{P}(T > n) = (1 - p_{couple})^n = (1 - (a + b - 2ab))^n \]

这个上界以指数速度衰减，衰减率为 \(1 - (a + b - 2ab)\)。例如，若 \(a = b = 0.5\)，则 \(p_{couple} = 0.5\)，上界为 \(0.5^n\)，表明链大约经过 \(\log_2(\epsilon^{-1})\) 步后，分布距离就会小于 \(\epsilon\)。

第六步：推广与极限唯一性的证明
上述例子展示了一个具体马尔可夫链的收敛速度估计。更一般地，对于任何有限状态、不可约且非周期的马尔可夫链，总可以构造一个耦合，使得耦合时间 \(T\) 几乎必然有限（即 \(\mathbb{P}(T < \infty) = 1\)）。一旦证明了这一点，由耦合不等式，对任意初始分布 \(\mu\) 和 \(\nu\) 启动的两个链，有：

\[\| \mu P^n - \nu P^n \|_{TV} \leq \mathbb{P}(T > n) \to 0 \quad (n \to \infty) \]

特别地，取 \(\nu = \pi\)（平稳分布），则 \(\nu P^n = \pi\)。于是我们证明了从任何初始分布出发，经过足够多步转移后，分布都会收敛到同一个极限分布 \(\pi\)，这即证明了极限分布的唯一性以及马尔可夫链的收敛性。耦合时间有限性的证明通常依赖于不可约性和非周期性，确保从任何两个状态出发，总存在一个有限长度的路径使得两个链能以正概率相遇。

总结：通过构造一个具有粘性性质的联合过程，耦合方法将复杂的分布收敛问题转化为对耦合时间 \(T\) 的分析。耦合不等式 \(\| \mu_n - \pi \|_{TV} \leq \mathbb{P}(T > n)\) 是核心工具。通过设计巧妙的耦合策略（如最大化每一步的相遇概率），我们可以得到收敛速度的明确上界（常为指数型），并简洁地证明极限分布的存在唯一性。此方法直观且强大，是研究马尔可夫链收敛性的基石技术之一。

马尔可夫链的耦合方法（续） 在先前对“马尔可夫链的耦合方法”的基本介绍中，我们已经了解了耦合的核心思想是构造两个（或多个）马尔可夫链的联合过程，使其各自的边际演化遵循给定的转移概率。现在，我们深入探讨其两大核心应用：估计收敛速度与证明分布的极限唯一性。我们将从一个具体例子出发，逐步展示其技术细节。 第一步：回顾目标与设定 假设我们有一个在有限状态空间 \( S \) 上的、不可约且非周期的马尔可夫链 \( (X_ n) \)，其转移矩阵为 \( P \)。该链具有唯一的平稳分布 \( \pi \)。我们关注其收敛速度，即如何量化 \( \| P(X_ n = j) - \pi_ j \| \) 随 \( n \) 衰减的快慢。耦合方法的核心是构造另一个从平稳分布 \( \pi \) 启动的链 \( (Y_ n) \)，即 \( Y_ 0 \sim \pi \)，并且 \( (Y_ n) \) 与 \( (X_ n) \) 具有相同的转移矩阵 \( P \)，但初始分布不同。 第二步：构造一个具体的耦合 我们的目标是在同一个概率空间上定义联合过程 \( (X_ n, Y_ n) \)，使得： 每个分量单独看都是一个转移矩阵为 \( P \) 的马尔可夫链。 \( X_ 0 \) 服从任意初始分布 \( \mu \)（我们关心的起点），而 \( Y_ 0 \sim \pi \)（平稳分布）。 定义一个“耦合时间” \( T = \inf\{ n \geq 0: X_ n = Y_ n \} \)。我们希望构造的联合过程具有“粘性”（也叫“重合后同步”性质）：一旦在某个时刻 \( n \) 满足 \( X_ n = Y_ n \)，则在所有后续时刻 \( m > n \) 都强制 \( X_ m = Y_ m \)。这意味着两个链在相遇后永久地保持同步运动。 一个经典且实用的构造是 最大耦合 （Maximal Coupling），其思想是在每一步都尽可能让两个链“走到同一个状态”，以最大化它们在下一步就相遇的概率。不过，为了直观理解，我们可以描述一个更简单的、基于转移概率的构造思想：在每个时间步 \( n \)： 如果 \( X_ n \neq Y_ n \)，我们可以让 \( X_ {n+1} \) 和 \( Y_ {n+1} \) 根据某个联合分布生成，这个联合分布的边际分布分别是 \( P(X_ {n+1} | X_ n) \) 和 \( P(Y_ {n+1} | Y_ n) \)，但可以存在相关性。一种常见策略是，以某个概率 \( \eta \) 尝试让它们跳到同一个状态（即“耦合尝试”），否则就独立地按照各自的转移概率跳跃。 如果 \( X_ n = Y_ n \)，则从下一步开始，强制 \( X_ {n+1} = Y_ {n+1} \)，并且都按照转移概率 \( P \) 从该共同状态出发。 第三步：利用耦合时间控制分布距离 耦合不等式是分析的关键。对于任意状态 \( j \)，事件 \( \{X_ n = j\} \) 可以分解为两部分：在时间 \( n \) 之前耦合已经发生（\( T \leq n \)）和尚未发生（\( T > n \)）。 \[ \mathbb{P}(X_ n = j) = \mathbb{P}(X_ n = j, T \leq n) + \mathbb{P}(X_ n = j, T > n) \] 由于在 \( T \leq n \) 时，由粘性性质可知 \( X_ n = Y_ n \)，所以 \( \mathbb{P}(X_ n = j, T \leq n) = \mathbb{P}(Y_ n = j, T \leq n) \)。而 \( Y_ n \) 始终服从平稳分布 \( \pi \)。因此： \[ \mathbb{P}(X_ n = j) - \pi_ j = \mathbb{P}(X_ n = j, T > n) - \mathbb{P}(Y_ n = j, T > n) \] 对两边取绝对值并对所有状态 \( j \) 求和，我们得到 全变差距离 的上界： \[ \| \mu_ n - \pi \| {TV} := \frac{1}{2} \sum {j} |\mathbb{P}(X_ n = j) - \pi_ j| \leq \mathbb{P}(T > n) \] 其中 \( \mu_ n \) 是 \( X_ n \) 的分布。这个不等式极为强大：它将两个分布的距离（一个涉及所有状态、难以直接计算的量）上界为耦合时间超过 \( n \) 的概率（一个单一事件的概率）。我们的任务转化为估计耦合时间 \( T \) 的尾部概率。 第四步：计算收敛速度的一个示例 假设链的状态空间是 \( \{1, 2\} \)，转移矩阵为： \[ P = \begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}, \quad 0 < a, b < 1 \] 其平稳分布为 \( \pi = (b/(a+b), a/(a+b)) \)。现在构造一个简单的耦合： 初始时，\( X_ 0 \) 任意（例如总是从状态1启动），\( Y_ 0 \sim \pi \)。 在每个时刻 \( n \)，如果 \( X_ n \neq Y_ n \)（即一个在1，另一个在2），则我们独立地投掷两枚硬币来决定它们的跳跃： 对于链 \( X \)：以概率 \( 1-a \) 留在当前状态，以概率 \( a \) 跳转。 对于链 \( Y \)：以概率 \( 1-b \) 留在当前状态，以概率 \( b \) 跳转。 如果它们状态不同，要使它们下一步相遇，唯一的方式是：处在状态1的那个链（假设是 \( X \)）必须跳走（概率 \( a \)），而处在状态2的那个链（\( Y \)）必须跳走（概率 \( b \)）。如果它们都跳，则它们会在下一步交换位置，但仍然不相等。要使它们相等，我们需要 其中一个链跳而另一个链不跳 。计算这个概率：\( X \) 跳 (\(a\)) 且 \( Y \) 不跳 (\(1-b\)) 的概率是 \( a(1-b) \)，或者 \( X \) 不跳 (\(1-a\)) 且 \( Y \) 跳 (\(b\)) 的概率是 \( (1-a)b \)。因此，在 \( X_ n \neq Y_ n \) 的条件下，下一步耦合成功（即 \( X_ {n+1} = Y_ {n+1} \)）的概率为 \( p_ {couple} = a(1-b) + (1-a)b = a + b - 2ab \)。如果耦合不成功（概率 \( 1 - p_ {couple} \)），则它们可能保持原状或交换，但仍是 \( X_ {n+1} \neq Y_ {n+1} \)。 一旦 \( X_ n = Y_ n \)，之后永久保持同步。 第五步：估计耦合时间的分布与收敛界 在这个耦合构造下，只要两个链尚未相同，每一步成功的概率是 \( p_ {couple} \)。因此，从任意不同初始状态出发，耦合时间 \( T \) 服从一个几何分布（如果首次尝试就成功，则 \( T=1 \)；否则需要多次尝试），其参数为 \( p_ {couple} \)。更精确地，\( T \) 是以概率 \( p_ {couple} \) 成功的几何随机变量，满足 \( \mathbb{P}(T > n) = (1 - p_ {couple})^n \)。 由耦合不等式，我们得到： \[ \| \mu_ n - \pi \| {TV} \leq \mathbb{P}(T > n) = (1 - p {couple})^n = (1 - (a + b - 2ab))^n \] 这个上界以指数速度衰减，衰减率为 \( 1 - (a + b - 2ab) \)。例如，若 \( a = b = 0.5 \)，则 \( p_ {couple} = 0.5 \)，上界为 \( 0.5^n \)，表明链大约经过 \( \log_ 2(\epsilon^{-1}) \) 步后，分布距离就会小于 \( \epsilon \)。 第六步：推广与极限唯一性的证明 上述例子展示了一个具体马尔可夫链的收敛速度估计。更一般地，对于任何有限状态、不可约且非周期的马尔可夫链，总可以构造一个耦合，使得耦合时间 \( T \) 几乎必然有限（即 \( \mathbb{P}(T < \infty) = 1 \)）。一旦证明了这一点，由耦合不等式，对任意初始分布 \( \mu \) 和 \( \nu \) 启动的两个链，有： \[ \| \mu P^n - \nu P^n \|_ {TV} \leq \mathbb{P}(T > n) \to 0 \quad (n \to \infty) \] 特别地，取 \( \nu = \pi \)（平稳分布），则 \( \nu P^n = \pi \)。于是我们证明了从任何初始分布出发，经过足够多步转移后，分布都会收敛到同一个极限分布 \( \pi \)，这即证明了极限分布的唯一性以及马尔可夫链的收敛性。耦合时间有限性的证明通常依赖于不可约性和非周期性，确保从任何两个状态出发，总存在一个有限长度的路径使得两个链能以正概率相遇。 总结 ：通过构造一个具有粘性性质的联合过程，耦合方法将复杂的分布收敛问题转化为对耦合时间 \( T \) 的分析。耦合不等式 \( \| \mu_ n - \pi \|_ {TV} \leq \mathbb{P}(T > n) \) 是核心工具。通过设计巧妙的耦合策略（如最大化每一步的相遇概率），我们可以得到收敛速度的明确上界（常为指数型），并简洁地证明极限分布的存在唯一性。此方法直观且强大，是研究马尔可夫链收敛性的基石技术之一。