马尔可夫链的耦合不等式

字数 2687 2025-12-08 14:54:48

马尔可夫链的耦合不等式

好的，我们开始讲解“马尔可夫链的耦合不等式”。我会循序渐进地展开这个概念。

首先，我们需要理解“耦合”在概率论中的一般含义。耦合是一种重要的概率技术，它将两个（或多个）概率结构（通常是随机过程）定义在同一个概率空间上，使得我们可以同时研究它们，并比较它们的差异。对于马尔可夫链，耦合特指将两条或多条（通常是起始点不同的）马尔可夫链构造在同一个概率空间上，让它们“一起”运行。

接下来，我们明确“马尔可夫链耦合不等式”的目标。这个不等式的主要目的是量化两个马尔可夫链分布收敛到同一分布（通常是平稳分布）的速度。它通过“耦合时间”这个随机变量来实现。耦合时间 定义为这两个链首次“相遇”（即处于相同状态）的时刻。一旦相遇，我们可以让它们在未来保持同步（即遵循相同的转移路径），此后它们的分布就完全相同了。

现在，我们逐步建立不等式。设我们有一个在状态空间S上的、具有平稳分布π的马尔可夫链。我们构造一个耦合：\((X_n, Y_n)_{n \ge 0}\)，其中：

\(X_n\) 是一个从初始分布 \(\mu\) 出发的该马尔可夫链。
\(Y_n\) 是一个从平稳分布 \(\pi\) 出发的该马尔可夫链（即 \(Y_0 \sim \pi\)，因此对所有n，\(Y_n \sim \pi\)）。
假设这个耦合的构造使得一旦 \(X_m = Y_m\) 对某个m成立，那么对所有 \(n \ge m\)，都有 \(X_n = Y_n\)。定义耦合时间 \(T = \inf \{ n \ge 0: X_n = Y_n \}\)，这是一个随机变量。

关键的推导步骤如下：

比较概率差：对于任何状态子集A，在任意时刻n，事件 \(\{X_n \in A\}\) 发生的概率与平稳概率 \(\pi(A)\) 之间的差异，可以通过耦合来分析。
构造事件：我们可以将事件分解：
\(\{X_n \in A\} = (\{X_n \in A\} \cap \{T \le n\}) \cup (\{X_n \in A\} \cap \{T > n\})\)。
由于在 \(T \le n\) 时，两条链在时刻n已经相遇并同步，所以 \(X_n = Y_n\)。因此，在 \(T \le n\) 的条件下，\(X_n\) 的分布和 \(Y_n\) 的分布相同，即平稳分布π。
概率分解：利用全概率公式：
\(P(X_n \in A) = P(X_n \in A, T \le n) + P(X_n \in A, T > n)\)。
对于第一项，由于在 \(\{T \le n\}\) 上 \(X_n = Y_n \sim \pi\)，所以 \(P(X_n \in A, T \le n) = P(Y_n \in A, T \le n) \le P(Y_n \in A) = \pi(A)\)。
实际上，更精确的分析是：
\(P(X_n \in A) - \pi(A) = [P(X_n \in A, T \le n) + P(X_n \in A, T > n)] - [P(Y_n \in A, T \le n) + P(Y_n \in A, T > n)]\)。
由于在 \(\{T \le n\}\) 上 \(X_n = Y_n\)，所以 \(P(X_n \in A, T \le n) = P(Y_n \in A, T \le n)\)。这两项相消。
得到基本不等式：经过上述抵消，我们得到：
\(P(X_n \in A) - \pi(A) = P(X_n \in A, T > n) - P(Y_n \in A, T > n)\)。
由于概率值在0和1之间，我们可以用绝对值不等式（三角不等式）得到：
\(|P(X_n \in A) - \pi(A)| \le P(X_n \in A, T > n) + P(Y_n \in A, T > n) \le 2P(T > n)\)。
但我们可以做得更好。注意到 \(P(X_n \in A, T > n) - P(Y_n \in A, T > n)\) 实际上等于 \(P(X_n \in A, T > n) - P(Y_n \in A, T > n)\)。由于 \(X_n\) 和 \(Y_n\) 在 \(T > n\) 时尚未相遇，它们的分布可能不同，但我们可以用绝对值放缩每一项不超过 \(P(T > n)\)，所以总和不超过 \(2P(T > n)\)。一个更紧的界可以通过取上确界得到。

最终，我们得到马尔可夫链耦合不等式的核心形式——总变差距离上界：
两个分布 \(\mu\) 和 \(\nu\) 的总变差距离定义为 \(||\mu - \nu||_{TV} = \sup_{A \subset S} |\mu(A) - \nu(A)|\)。
将上述推导中的 \(P(X_n \in A)\) 视为从 \(\mu\) 出发n步后的分布 \(\mu P^n\) (A)，而 \(\pi(A)\) 是平稳分布，我们有：

\[||\mu P^n - \pi||_{TV} \le P(T > n) \]

注意：这里 \(P(T > n)\) 是耦合时间T超过n的概率。这个不等式是耦合方法的核心：马尔可夫链在时刻n的分布与平稳分布的距离，不超过这两条链在时刻n尚未相遇的概率。

总结与应用：

意义：这个不等式将收敛性的分析转化为对一个随机变量（耦合时间T）尾部概率 \(P(T > n)\) 的分析。如果我们能构造一个好的耦合，使得耦合时间T以大概率很快地变小（例如，T有指数衰减的尾概率），我们就能证明马尔可夫链以相应的速度（如几何速率）收敛到平稳分布。
关键：不等式的紧致性依赖于耦合构造的好坏。最优的耦合应使 \(P(T > n)\) 尽可能小。通常我们会寻求使 \(E[T]\) 最小或使 \(P(T > n)\) 衰减最快的耦合。
延伸：基于此不等式，可以推导出马尔可夫链的收敛速率、混合时间等关键指标。它是分析马尔可夫链蒙特卡洛方法收敛速度的基石工具之一。

因此，马尔可夫链耦合不等式是一个强有力的工具，它通过一个巧妙的概率构造（耦合），将抽象的分布收敛问题，转化为一个更直观的、关于两个随机过程首次相遇时间的概率问题。

马尔可夫链的耦合不等式好的，我们开始讲解“马尔可夫链的耦合不等式”。我会循序渐进地展开这个概念。首先，我们需要理解“耦合”在概率论中的一般含义。耦合是一种重要的概率技术，它将两个（或多个）概率结构（通常是随机过程）定义在同一个概率空间上，使得我们可以同时研究它们，并比较它们的差异。对于马尔可夫链，耦合特指将两条或多条（通常是起始点不同的）马尔可夫链构造在同一个概率空间上，让它们“一起”运行。接下来，我们明确“马尔可夫链耦合不等式”的目标。这个不等式的主要目的是量化两个马尔可夫链分布收敛到同一分布（通常是平稳分布）的速度。它通过“耦合时间”这个随机变量来实现。耦合时间定义为这两个链首次“相遇”（即处于相同状态）的时刻。一旦相遇，我们可以让它们在未来保持同步（即遵循相同的转移路径），此后它们的分布就完全相同了。现在，我们逐步建立不等式。设我们有一个在状态空间S上的、具有平稳分布π的马尔可夫链。我们构造一个耦合：\( (X_ n, Y_ n)_ {n \ge 0} \)，其中： \( X_ n \) 是一个从初始分布 \(\mu\) 出发的该马尔可夫链。 \( Y_ n \) 是一个从平稳分布 \(\pi\) 出发的该马尔可夫链（即 \(Y_ 0 \sim \pi\)，因此对所有n，\(Y_ n \sim \pi\)）。假设这个耦合的构造使得一旦 \(X_ m = Y_ m\) 对某个m成立，那么对所有 \(n \ge m\)，都有 \(X_ n = Y_ n\)。定义耦合时间 \(T = \inf \{ n \ge 0: X_ n = Y_ n \}\)，这是一个随机变量。关键的推导步骤如下：比较概率差：对于任何状态子集A，在任意时刻n，事件 \(\{X_ n \in A\}\) 发生的概率与平稳概率 \(\pi(A)\) 之间的差异，可以通过耦合来分析。构造事件：我们可以将事件分解： \(\{X_ n \in A\} = (\{X_ n \in A\} \cap \{T \le n\}) \cup (\{X_ n \in A\} \cap \{T > n\})\)。由于在 \(T \le n\) 时，两条链在时刻n已经相遇并同步，所以 \(X_ n = Y_ n\)。因此，在 \(T \le n\) 的条件下，\(X_ n\) 的分布和 \(Y_ n\) 的分布相同，即平稳分布π。概率分解：利用全概率公式： \(P(X_ n \in A) = P(X_ n \in A, T \le n) + P(X_ n \in A, T > n)\)。对于第一项，由于在 \(\{T \le n\}\) 上 \(X_ n = Y_ n \sim \pi\)，所以 \(P(X_ n \in A, T \le n) = P(Y_ n \in A, T \le n) \le P(Y_ n \in A) = \pi(A)\)。实际上，更精确的分析是： \(P(X_ n \in A) - \pi(A) = [ P(X_ n \in A, T \le n) + P(X_ n \in A, T > n)] - [ P(Y_ n \in A, T \le n) + P(Y_ n \in A, T > n) ]\)。由于在 \(\{T \le n\}\) 上 \(X_ n = Y_ n\)，所以 \(P(X_ n \in A, T \le n) = P(Y_ n \in A, T \le n)\)。这两项相消。得到基本不等式：经过上述抵消，我们得到： \(P(X_ n \in A) - \pi(A) = P(X_ n \in A, T > n) - P(Y_ n \in A, T > n)\)。由于概率值在0和1之间，我们可以用绝对值不等式（三角不等式）得到： \(|P(X_ n \in A) - \pi(A)| \le P(X_ n \in A, T > n) + P(Y_ n \in A, T > n) \le 2P(T > n)\)。但我们可以做得更好。注意到 \(P(X_ n \in A, T > n) - P(Y_ n \in A, T > n)\) 实际上等于 \(P(X_ n \in A, T > n) - P(Y_ n \in A, T > n)\)。由于 \(X_ n\) 和 \(Y_ n\) 在 \(T > n\) 时尚未相遇，它们的分布可能不同，但我们可以用绝对值放缩每一项不超过 \(P(T > n)\)，所以总和不超过 \(2P(T > n)\)。一个更紧的界可以通过取上确界得到。最终，我们得到马尔可夫链耦合不等式的核心形式—— 总变差距离上界：两个分布 \(\mu\) 和 \(\nu\) 的总变差距离定义为 \(||\mu - \nu|| {TV} = \sup {A \subset S} |\mu(A) - \nu(A)|\)。将上述推导中的 \(P(X_ n \in A)\) 视为从 \(\mu\) 出发n步后的分布 \(\mu P^n\) (A)，而 \(\pi(A)\) 是平稳分布，我们有： \[ ||\mu P^n - \pi||_ {TV} \le P(T > n) \] 注意：这里 \(P(T > n)\) 是耦合时间T超过n的概率。这个不等式是耦合方法的核心：马尔可夫链在时刻n的分布与平稳分布的距离，不超过这两条链在时刻n尚未相遇的概率。总结与应用：意义：这个不等式将收敛性的分析转化为对一个随机变量（耦合时间T）尾部概率 \(P(T > n)\) 的分析。如果我们能构造一个好的耦合，使得耦合时间T以大概率很快地变小（例如，T有指数衰减的尾概率），我们就能证明马尔可夫链以相应的速度（如几何速率）收敛到平稳分布。关键：不等式的紧致性依赖于耦合构造的好坏。最优的耦合应使 \(P(T > n)\) 尽可能小。通常我们会寻求使 \(E[ T ]\) 最小或使 \(P(T > n)\) 衰减最快的耦合。延伸：基于此不等式，可以推导出马尔可夫链的收敛速率、混合时间等关键指标。它是分析马尔可夫链蒙特卡洛方法收敛速度的基石工具之一。因此，马尔可夫链耦合不等式是一个强有力的工具，它通过一个巧妙的概率构造（耦合），将抽象的分布收敛问题，转化为一个更直观的、关于两个随机过程首次相遇时间的概率问题。