一种简单的并行分布式采样技术：

局部 Glauber 动力学

摘要

采样是许多领域的重要工具：从机器学习和组合优化到计算物理和生物学。 采样算法的核心类别是马尔可夫链蒙特卡罗方法，该方法基于以所需采样分布作为其平稳分布的马尔可夫链的构造。 许多传统的马尔可夫链，例如 Glauber 动力学，随着维度的增加而不能很好地扩展。 为了解决这个缺点，我们提出了一种基于格劳伯动力学的简单局部更新规则，该规则产生了用于从吉布斯分布采样的高效并行和分布式算法。

具体来说，我们提出了一个马尔可夫链，当满足吉布斯分布的 Dobrushin 条件时，它会在 $O(\log n)$ 轮中混合。 这改进了 Feng、Sun 和 Yin [PODC'17] 的 LubyGlauber 算法，该算法需要 轮，以及他们的 LocalMetropolis 算法，该算法需要 $O(\mathrm{\Delta }\log n)$ 轮。在 $O(\log n)$ 轮中收敛，但需要相当强的混合条件。 这里，$n$表示诱导吉布斯分布的图形模型中的节点数，$\mathrm{\Delta }$表示其最大度。 特别是，我们的方法可以对任何 $\alpha >2$ 在 $O(\log n)$ 轮中使用 $\alpha \mathrm{\Delta }$ 颜色采样均匀的正确着色，这几乎与顺序 Glauber 动力学的阈值匹配，提高了 Feng 等人的 $\alpha >2+\sqrt{2}$ 阈值

1简介

本地可检查标签 (LCL) [NS95]问题已被广泛研究了三十多年[Lin87]。 然而，从此类拼箱的解决方案空间中进行采样并没有引起太多关注，并且仅由最近的工作[FSY17]进行了研究，尽管其动机众多，我们将在下面概述。

马尔可夫链蒙特卡罗方法

马尔可夫链蒙特卡罗（MCMC）方法是采样算法的核心类，即根据一定的概率分布从地面集中随机抽取元素。 它的工作原理是构建一个马尔可夫链，以目标采样分布作为其平稳分布。 在称为混合时间的多个步骤内，马尔可夫链收敛；那么它的状态（大约）遵循这个分布。 除了这种通用采样方法的内在兴趣外，特别是对于简单采样技术失败的复杂分布，MCMC 方法在各个领域产生了有效的近似算法：枚举组合学（由于采样和计数之间建立了基本联系）由 Jerrum、Valiant 和 Vazirani [JVV86])、组合优化中的模拟退火 [NSS86]、蒙特卡洛模拟 [MRR+53]在统计物理学中，计算机器学习中的贝叶斯推理[ADFDJ03]等棘手的积分。

并行和分布式采样

当面对高维数据时，传统（精确）方法很快就会变得棘手，MCMC 方法的使用尤其重要。 此类数据集不仅越来越频繁，而且对于许多应用程序的成功至关重要。 例如，在机器学习中，高维模型有助于提高可表达性，从而提高可预测性。 因此，MCMC 算法随着维度的增加而良好地扩展是至关重要的。 然而，对于大多数顺序方法而言，情况并非如此，因为它们逐一处理和更新变量，即每个步骤一个站点。 为了加速采样过程，可以通过将变量分布在多个处理器上来并行马尔可夫链更新。 在其他设置中，例如分布式机器学习，变量（与变量相关的数据）可能已经自然地分布在多台机器中，并且如果它们一开始就适合将它们聚合到一台机器中，那么将它们聚合到一台机器中的开销将是站不住脚的。

本地抽样

在任何一种情况下，为了避免通信和协调的开销，需要马尔可夫链的本地更新规则：机器必须能够在不知道其他机器上变量的所有值的情况下更改其变量的值。 然而，系统中所有变量的联合分布必须收敛到某个分布。 这个局部采样问题是在 Feng、Sun 和 Yin [FSY17] 最近的工作中引入的，其标题询问“什么可以在本地采样？”。 我们通过提供一种简单且通用的采样技术来解决这个问题——局部格劳伯动力学，在部分 1.2中非正式介绍> 并在 Section 2 中正式描述 - 适用于广泛的发行版，如 Section< 中所述/t8>1.1。 这使我们离回答这个问题又近了一步，从而实现了普遍了解可以在本地采样的目标。 除了它的许多实际影响之外，特别是在分布式机器学习领域，这还为我们提供了关于问题的局部性的理论见解，其系统研究是由 Linial 的开创性工作发起的[ Lin87] 以及 Naor 和 Stockmeyer [NS95]，标题简洁“什么可以在本地计算？”。

1.1我们的结果和相关工作

为了演示的简洁性和可理解性，我们根据顺序采样最受关注的特殊情况来陈述和证明我们的主要结果：对图的正确着色进行采样。 我们参考[FV07]进行有关正确颜色顺序采样的调查。 然而，我们的结果适用于更一般的分布集，正如本节末尾的评论中所解释的那样。 请注意，Feng、Hayes 和 Yin [FHY18] 独立且同时得出了相同的结果。

Theorem 1.1.

对于具有最大度 $\mathrm{\Delta }$ 的 $n$ 节点图，可以在 $O\left(\log \left(\frac{n}{\epsilon }\right)\right)$ 轮中在总变化距离 $\epsilon >0$ 范围内对其进行统一的适当 $q$ 着色，其中 $q=\alpha \mathrm{\Delta }$ 适用于任意 $\alpha >2$ 。

我们的并行分布式采样算法改进了 Feng、Sun 和 Yin [FSY17] 的 LubyGlauber 算法，该算法需要 $O\left(\mathrm{\Delta }\log \left(\frac{n}{\epsilon }\right)\right)$ 轮，并且它们的 LocalMetropolis算法，在$O\left(\log \left(\frac{n}{\epsilon }\right)\right)$轮内收敛，但需要更强的$\alpha >2+\sqrt{2}$混合条件。 他们指出“我们也相信$2+\sqrt{2}$阈值对于这个[LocalMetropolis]链具有一定的意义，就像Dobrushin条件对于格劳伯动力学一样。”，因此暗示这个值是他们接近的障碍。 这也被认为是最简单的树特殊情况所证明，该树导致其算法具有相同的阈值。 我们的结果消除了额外的 $\sqrt{2}$，同时不会对回合复杂性造成任何损失，并且更新规则更加简单和自然。 我们的证明不仅更简单、更短，而且我们的算法也是渐近最好的，因为由于变量之间的指数相关性，存在 $\mathrm{\Omega }\left(\log \left(\frac{n}{\epsilon }\right)\right)$ 下界 [GJL17, FSY17]。

$\alpha >2$的阈值对应于Dobrushin条件，因此几乎与$2\mathrm{\Delta }+1$处的顺序格劳伯动力学[Jer95，SS97]的阈值匹配。 换句话说，我们提出了一种完全并行化 Glauber 动力学的技术，将混合时间从 $\text{poly}n$ 步加快到 $O(\log n)$ 轮。 就所需的颜色数量而言，Dobrushin 的条件可能会被削弱：Vigoda [Vig00] 和最近的两幅作品 [CM18, DPP18] 表明，当诉诸不同的颜色时，高度非局部马尔可夫链，$\alpha =\frac{11}{6}$就足够了。 这就提出了一个问题：高效的分布式算法本质上是否需要停留在多布鲁辛条件下，这意味着这个界限是采样过程局部性所固有的，或者我们的阈值是否是我们可能的次优动态的产物。

Remark 1.2.

事实上，我们的技术直接应用于从马尔可夫随机场引起的吉布斯分布中采样 如果满足 Dobrushin 的条件 [Dob68]。 更一般地说，它可以用于从任何局部（即恒定半径）约束满足问题中进行采样，这对于条件独立联合分布来说是通用的，这归因于 Hammersley-Clifford 的基本定理[HC71]。 此外，我们在这里提出的证明涵盖了这些更一般情况下出现的所有困难，因此可以直接进行调整。 我们将这种概括推迟到论文的完整版本中。

1.2 我们的采样技术和相关方法

在过去的几年中，已经提出了几种并行化顺序马尔可夫链的方法。 它们中的大多数依赖于重型协调机制，具有特殊用途，和/或不提供任何理论保证。 下面，我们在着色的背景下简要概述两种最有前途且更通用的并行和分布式采样技术。

最自然的方法遵循标准的去中心化方法，也由 [FSY17] 在 LubyGlauber 算法中实现：一组独立的节点（例如，适当着色的颜色类） ）同时更新它们的颜色[FSY17]，确保没有两个相邻节点同时改变它们的颜色。 这种方法主要受到覆盖所有节点所需的独立集数量可能很大的限制，这会减慢混合速度。 特别是，混合时间中的乘法$\mathrm{\Delta }$项似乎是不可避免的[GLGG11，FSY17]。 在团的最坏情况下，这种方法会退回到顺序采样，一个接一个地更新节点。 此外，该方法需要计算一个独立的集合，这会导致大量的额外通信和协调。

[NSWA08，YXQ09，FSY17]追求正交方向，其中引入了同时更新所有节点颜色的方法。 一个例子是 [FSY17] 的 LocalMetropolis 算法。 然而，这种极端的并行性的代价是要么在平稳分布中引入偏差，导致着色不均匀[NSWA08，YXQ09]，要么必须要求更强的混合条件 [2017财政年度]。

我们的本地采样技术

我们的目标是这两种方法之间的中间立场，其动机是以下观察：我们不需要防止相邻节点的同时更新，只需要防止相邻节点的同时冲突更新。 首先阻止两个相邻节点在同一轮中选择新颜色似乎限制性太大，特别是因为两个节点不太可能瞄准相同的新颜色。 另一方面，如果所有节点同时更新其颜色，则预计节点将与其至少一个邻居发生冲突，从而阻碍进度。

我们通过引入标记概率在两种极端情况之间进行插值，以便只有一小部分节点的邻居预计会更新颜色，因此，在最坏的情况下，只有这些邻居会与其更新发生冲突。 具体来说，我们提出了以下通用采样方法，我们称之为局部格劳伯动力学：在每一步中，每个变量以一定的（低）概率独立地随机标记自己。 如果被标记，它会随机采样一个提案，并与其邻居检查该提案是否会导致与其当前状态或新提案（如果有）发生冲突。 如果存在冲突，变量将回滚并保持其当前状态，否则状态将被更新。 与顺序采样相反，顺序采样每步只有一个变量更新其值，这里同时更新其值的变量的预期数量为 $\mathrm{\Omega }(n)$，从而实现 $O(n\log n)$ 所需的加速，比如说$O(\log n)$。 当然，主要的技术方面在于证明这个简单的更新规则在$O(\log n)$轮中收敛到均匀分布，我们在部分2<中证明了这一点/t3>。

1.3 符号和基本知识

模型

我们使用标准分布式消息传递模型来研究局部性：Linial [Lin87]引入的$\mathrm{𝖫𝖮𝖢𝖠𝖫}$模型，定义如下。 给定 $n$ 节点上具有最大度 $\mathrm{\Delta }$ 的图 $G=(V,E)$，计算按轮进行。 在每一轮中，每个节点都可以向其每个邻居发送消息。 我们不限制消息大小，但对于我们提出的算法，$O(\log n)$ 位消息就足够了。 在计算结束时，每个节点$v$输出一种颜色。 主要关注的数量是回合复杂度，即直到所有节点的联合输出满足某个条件为止的回合数。 我们假设所有节点都知道$\log n$和$\mathrm{\Delta }$。

马尔可夫链

我们考虑马尔可夫链$\text{X}={\left(X^{(t)}\right)}_{t\ge 0}$，其中$X^{(t)}={\left(X_v^{(t)}\right)}_{v\in V}\in {[q]}^V$是$t$轮中图的着色。我们将省略圆形索引，并使用 $X={(X_v)}_{v\in V}\in {[q]}^V$ 进行时间 $t$ 的着色，使用 $X^{\prime }={(X_v^{\prime })}_{v\in V}\in {[q]}^V$ 进行时间 $t+1$ 的着色，对于而是 $t\ge 0$。

混合时间

对于具有静态分布 $\mu$ 的马尔可夫链 ${\left(X^{(t)}\right)}_{t\ge 0}$，让 ${\pi }_{\sigma }^{(t)}$ 表示该链在时间 $t\ge 0$ 时的随机着色 $X^{(t)}$ 的分布，条件是 $X^{(0)}=\sigma$。 混合时间 ${\tau }_{\text{mix}}(\epsilon )={\max }_{\sigma \in \mathrm{\Omega }}\min \left\{t\ge 0:d_{\text{TV}}({\pi }_{\sigma }^{(t)},\mu )\right\}$ 定义为使马尔可夫链 $\epsilon$ 接近（就总变化距离而言）其平稳分布 $\mu$，无论$X^{(0)}$。 $\mathrm{\Omega }$ 上两个分布 $\mu ,\nu$ 之间的总变异距离定义为 $d_{\text{TV}}(\mu ,\nu )={\sum }_{\sigma \in \mathrm{\Omega }}\frac{1}{2}\left|\mu (\sigma )-\nu (\sigma )\right|$。

路径耦合

Bubley 和 Dyer 的路径耦合引理[BD97，定理 1]（另请参阅[FSY17，引理 4.3])产生了一个特别设计联轴器的简单方法。 在简化版本中，它表示仅针对相邻的着色对（即在一个节点上不同）定义马尔可夫链的耦合就足够了。 一个耦合步骤之后不同节点的预期数量可用于限制马尔可夫链的混合时间。

Lemma 1.3 （路径耦合[BD97]，简化）。

对于$\sigma ,{\sigma }^{\prime }\in {[q]}^V$，令$\varphi (\sigma ,{\sigma }^{\prime }):=|\{v\in V:{\sigma }_v\ne {\sigma }_v^{\prime }\}|$。 如果存在马尔可夫链的耦合 $(X,Y)\to (X^{\prime },Y^{\prime })$，且仅定义为 $(X,Y)$ 与 $\varphi (X,Y)=1$，满足 $𝔼[\varphi (X^{\prime },Y^{\prime })\mid X,Y]\le 1-\delta$ 的某个 ，那么 ${\tau }_{\text{mix}}(\epsilon )=O\left(\frac{1}{\delta }\cdot \log \left(\frac{n}{\epsilon }\right)\right)$。

2 本地格劳伯动力学

当地格劳伯动力学

我们定义一轮中从 $X={(X_v)}_{v\in V}$ 到 $X^{\prime }={(X_v^{\prime })}_{v\in V}$ 的转换，如下所示。 每个节点$v\in V$以概率独立标记自己。 如果它被标记，它会独立于所有其他节点，均匀随机地提出新颜色$c_v\in [q]$。 如果此建议颜色不会导致与任何邻居的当前颜色和建议颜色发生冲突，即任何 $u\in N(v)$ 的 $c_v\notin {\bigcup }_{u\in N(v)}\{X_u,c_u\}$ 和 $c_u\notin \{X_v,c_v\}$，则 $v$ 接受颜色 $c_v$，从而设置 $X_v^{\prime }=c_v$。 否则，$v$ 保持其当前颜色，即设置$X_v^{\prime }=X_v$。 请注意，条件 $c_v\notin {\bigcup }_{u\in N(v)}\{X_u,c_u\}$ 对于保证马尔可夫链的可逆性是必要的。

固定分布

局部格劳伯动力学是遍历的：它是非周期性的，因为总是存在不改变任何颜色的正概率，并且是不可约的，因为可以从任何颜色达到任何（适当的）颜色。 而且，链条可能从不正确的颜色开始，但它永远不会从正确的颜色移动到不正确的颜色，也就是说，它会吸收到正确的颜色。 很容易验证这种局部格劳伯动力学，由于其对称更新规则，满足均匀分布的详细平衡方程，这意味着从 $X$ 到 $X^{\prime }$ 的过渡具有与从 $X^{\prime }$ 到 $X$ 过渡以获得正确着色的概率相同。 因此，该链是可逆的，并且在所有适当的着色上具有均匀分布作为独特的固定分布。

混合时间

通俗地说，路径耦合引理表示，如果对于在一个节点上不同的所有 $X$ 和 $Y$，我们可以定义一个耦合 $(X,Y)\to (X^{\prime },Y^{\prime })$ ，这样$X^{\prime }$ 和 $Y^{\prime }$ 不同的节点的预期数量从上面开始远离 1，那么链很快收敛。 在 Section 2.1 中，我们正式描述了这种路径耦合；在 Section 2.2 中，我们列出了一个节点在一个耦合步骤后具有两种不同颜色的必要条件（但不一定是充分条件），然后在 Section 2.3 中，根据 $\alpha$ 以某个常数 约束不同节点的预期数量 $1-\delta$。 应用引理1.3得出定理1.1.

2.1 路径耦合说明

我们查看仅在节点 $v_0\in V$ 处不同的两种颜色 $X$ 和 $Y$。 也就是说，$r=X_{v_0}\ne Y_{v_0}=b$，对于某些 $r\ne g\in [q]$，我们自然会分别将其称为红色和蓝色，以及 $X_v=Y_v$，对于所有 $v\ne v_0\in V$ >。 接下来，我们将解释每个节点 $v\in V$ 如何提出一对 $(c_v^X,c_v^Y)$ 新提案，然后根据本地 Glauber 动力学规则接受或拒绝这些提案。

标记

在两条链中，每个节点 $v\in V$ 都以概率 $\gamma$ 独立标记，在两条链中使用相同的随机性。 在下文中，我们将注意力仅限于标记的节点；未标记的节点被认为将其当前颜色建议为新颜色，即 $c_v^X=X_v$ 和 $c_v^Y=Y_v$。

一致、镜像和翻转的提案

我们介绍了两种可能的方式来对节点$v$的提案进行采样：一致和镜像。 对于一致的提案，两个链都提出相同的随机选择颜色，即 u.a.r. 的 $c_v^X=c_v^Y=c$。 $c\in [q]$。 对于镜像提案，如果两条链既不是红色也不是蓝色，则分配相同的随机提案，否则分配翻转提案（即，红色分配给一个链，蓝色分配给另一条链）。 更正式地说，对于 u.a.r，如果 $c\in \{r,b\}$ 和 $\overline{c}$ 中的元素在 $\{r,b\}\setminus \{c\}$ 中，则 $c_v^X=c$ 和 $c_v^Y=\overline{c}$ ；如果 $c\notin \{r,b\}$ 中的元素在 中，则 $c_v^X=c_v^Y=c$ 。 $c\in [q]$。 如果$c_v^X\ne c_v^Y$，我们就说$v$已经翻转了个提案。 请注意，我们说镜像提案是指镜像采样的过程，如果镜像采样的结果是一个节点在两条链中提出了不同的颜色，我们就说翻转。

广度优先的提案分配

令 $B=\{v\in V\setminus \{v_0\}:X_v\in \{r,b\}\}\subseteq V\setminus \{v_0\}$ 为当前颜色为红色或蓝色的节点 $v\ne v_0$ 的集合，以及 $K=\left({\bigcup }_{v\in B}{N}^{+}(v)\right)\setminus \{v_0\}$ 其包含邻域，没有 $v_0$，其中$N^{+}(v):=N(v)\cup \{v\}$。 我们暂时忽略这个集合$K$，并关注与红色或蓝色节点不相邻的标记节点集合$S\subseteq V\setminus K$（可能除了$v_0$)。 通俗地说，我们将以广度优先的方式遍历这些节点，增加到节点$v_0$的距离$d\ge 0$，并逐层修复它们的提案，但推迟节点的分配（尚未）与具有翻转提案的节点相邻，如下所示。 我们重复地将最后一层中具有翻转提案的节点的所有（仍然剩余的）节点添加到新层，并对它们的提案进行镜像采样，从而仅对具有翻转提案的节点执行广度优先分配。 所有剩余节点一致地对其提案进行采样。 请注意，这特别保证了仅当节点不与具有翻转提案的节点相邻时才对节点进行一致采样。

更正式地说，这可以描述如下。 我们定义了 $M^0=F^0=\{v_0\}$，即使 $v_0$ 没有标记。 对于节点$v_0$，如果标记，则提案的采样是一致的。 对于$d\ge 1$和$v\in M^d$，提案被镜像采样。 对于后续层，我们将注意力限制在仅具有翻转提案的 $M^d$ 中节点的（新）邻居，即，考虑 $F^d=\{v\in M^d:c_v^X\ne c_v^Y\}$ 的 $M^{d+1}=N\left(F^d\right)\setminus {\bigcup }_{i=0}^d{M}^d$ 。

对于所有剩余的（标记的）节点，即 $S\setminus M$ 中的节点和 $K$ 中的节点，提案的采样是一致的。 有关这种基于广度优先的方法的说明，请参见图 1。

接受建议

链$X$和$Y$中的提议${(c_v^X)}_{v\in V}$和${(c_v^Y)}_{v\in V}$根据局部格劳伯动力学规则被接受或拒绝，从而导致着色$X^{\prime },Y^{\prime }\in {[q]}^V$。

图1： 两个在 $v_0\in M^0$ 处不同的链的 $d\ge 0$ 的广度优先层 $M^d$。 磁盘颜色对应于节点的当前颜色，其中黑色表示除红色和蓝色之外的任何颜色。 节点周围方框的颜色显示该节点建议的颜色，其中白色代表任何颜色（也可能是红色或蓝色，但保持一致）。 虚线框表示具有翻转提案的节点集$F^d$。 请注意，节点 $v$ 出现在第 4 层，尽管它到 $v_0$ 的距离为 3。 这是因为我们仅在具有翻转提案的节点上执行广度优先分配。 $v$的邻居$u$没有翻转提案，因此在$M^2\setminus F^2$中，这意味着$u$的邻居没有被添加到下一层。 只有$v$的邻居$w\in F^3$导致$v$被添加到$M^4$。

2.2 联轴器的特性

主要观察如下。 如果我们暂时忽略当前颜色为红色和蓝色的节点，则可以认为 $X^{\prime }$ 和 $Y^{\prime }$ 只能在与 $v_0$ 不同的节点上不同，如果其提案被推翻。 然而，翻转提案只有在对提案进行镜像采样时才会出现，只有当前一层中存在具有翻转提案的节点时才会发生这种情况（由于我们分配提案的广度优先顺序）。 因此，仅当 $G$ 中存在从 $v_0$ 到该节点的路径（由具有翻转提案的节点组成）（称为 翻转路径)时，节点才会导致不一致。 。

接下来，我们将通过翻转路径使这种直觉更加精确，分两部分：对于 $S$ 中的节点（如果与具有翻转提案的节点相邻，则镜像地采样其提案）在 引理中 2.1 以及引理 中$K$中的节点（始终一致地对其提案进行采样） 2.2。 有关这两种情况的说明，请参见图2。

Lemma 2.1.

如果 $X^{\prime }$ 和 $Y^{\prime }$ 在 $v\ne v_0\in S$ 处不同，则在 $G$ 中存在一条长度为 $\mathrm{\ell }\ge 1$ 的翻转路径 $(v_0,\mathrm{\dots },v_{\mathrm{\ell }}=v)\in F^0\times \mathrm{\cdots }\times F^{\mathrm{\ell }}$，其附加属性是 $v$ 的提案与这条路径上在两条链中看到的最后一种颜色（红色和蓝色）相反。 更正式地说，$c_Y=c_v^X\ne c_v^Y=c_X$，其中 $c_X=c_{v_{\mathrm{\ell }-1}}^X$ 和 $c_Y=c_{v_{\mathrm{\ell }-1}}^Y$ 如果 $\mathrm{\ell }>1$，以及 $c_X=X_{v_0}$ 和 $c_Y=Y_{v_0}$如果$\mathrm{\ell }=1$。

证明。

我们首先认为 $v$ 的提案必须在两条链中被翻转并接受。 简单地说，在两个链中接受一致的提案或在两个链中拒绝都会导致 $X_v^{\prime }=Y_v^{\prime }$。 此外，观察到，根据结构，翻转的提案要么在两个链中被接受，要么在两个链中被拒绝，因为翻转改变了红色和蓝色的角色，但没有改变整体行为。 事实上，假设不失一般性，$c_v^X=c\in \{r,b\}$ 被 $X$ 拒绝。 因此，特别是 $v$ 在 $X$ 中具有具有当前颜色或建议 $c$ 的邻居 $u$。 由于我们的注意力仅限于集合 $S$，而该集合中没有任何相邻节点的当前颜色为红色或蓝色，因此除了 $v_0$ 以外，$u=v_0$ 或 $u$ 都会提议 $c$。因此，$u$ 要么具有不同的当前颜色（如果是 $u=v_0$），要么具有镜像提议（如果是 $v\in F^d$，那么 $u\in M^{d^{\prime }}$ 对于某些 $d^{\prime }\le d+1$，因为根据我们以广度优先方式分配提议的方法，$v$ 的翻转提议最迟会导致 $u$ 被添加到后续层），从而导致翻转提议。 因此，$v$在$Y$中的提案$\overline{c}$将被$Y$拒绝，因为$u=v_0\in N(v)$有颜色$\overline{c}$或$u\in N(v)$提议$\overline{c}$。

因此，仍然需要排除在一个链中接受而在另一个链中拒绝的一致提案的情况。 对于矛盾，假设 $v$ 在两个链中提出相同的颜色 $c_v$，并且它在一个链中被接受而在另一个链中被拒绝。 由于 $X_v=Y_v$ 和 $c_v^X=c_v^Y$，只有当 $v$ 与 $v_0$ 或至少一个具有翻转提案的节点相邻时，才会发生这种情况，否则，$v$ 包容性邻域中的所有提案和所有当前颜色都将相同，从而导致两条链中的行为相同。 在这两种情况下，$v\in M^d$对于某些$d\ge 1$来说，这意味着它的提案是镜像采样的。 因此，$c_v\notin \{r,b\}$，否则提案将被推翻。 现在，由于 $v$ 的当前颜色和 $v$ 的建议都不是红色或蓝色，并且 $v$ 的邻居的颜色或建议只有在以下情况下才能不同：涉及红色或蓝色时，两条链中的提案要么被接受，要么被拒绝。 由此可见，实际上只有 $S$ 中具有被两个链都接受的翻转提案的节点才能在 $X^{\prime }$ 和 $Y^{\prime }$ 中具有不同的颜色。

根据图层的构造，并且由于 $v\in F^{\mathrm{\ell }}$ 对于某个 $\mathrm{\ell }\ge 1$ 而言，必然存在一个连接 $v_0$ 和 $v$ 的节点序列 $v_1\in F^1,\mathrm{\dots },v_{\mathrm{\ell }-1}\in F^{\mathrm{\ell }-1}$ 在 $G$ 中：长度为 $\mathrm{\ell }$ 的翻转路径。 此外，只有当提议的颜色与路径上看到的颜色（红色或蓝色）相反（如果是 $\mathrm{\ell }>1$ 则为提议颜色，如果是 $\mathrm{\ell }=1$ 则为 $v_0$ 的当前颜色）时，链中的提议才会被接受。 ∎

Lemma 2.2.

如果 $X^{\prime }$ 和 $Y^{\prime }$ 在 $v\ne v_0\in K$ 处不同，则在 $G$ 中存在一条长度为 $\mathrm{\ell }\ge 1$ 的路径 $(v_0,\mathrm{\dots },v_{\mathrm{\ell }}=v)\in F^0\times \mathrm{\cdots }\times F^{\mathrm{\ell }-1}\times K$，称为几乎翻转路径，其附加属性是 $v$ 的提案不是红色就是蓝色，即 $c_v=c_v^X=c_v^Y\in \{r,b\}$。

证明。

由于根据耦合的定义，$v\in K$ 对其建议的采样是一致的，因此 $X^{\prime }$ 和 $Y^{\prime }$ 只有在 $v\ne v_0$ 中的建议在一个链中被接受而在另一个链中被拒绝时才会有差异。 仅当 $v$ 与 $v_0$ 或至少一个具有翻转提案的节点相邻时，才会发生这种情况。 否则，$v$ 包容性邻域中的所有提案和所有当前颜色都将相同，从而导致相同的行为。 因此，对于某些 $d\ge 0$,$v$ 与某些 $u\in F^d$ 相邻。 通过构造层，在 $G$ 中必须存在连接 $v_0$ 到 $v$ 的一系列节点 $v_1\in F^1,\mathrm{\dots },v_{\mathrm{\ell }-1}=u\in F^{\mathrm{\ell }-1}$：一条几乎翻转的路径长度$\mathrm{\ell }=d+1$。 请特别注意，因为根据定义，$B$ 中节点的邻居是一致采样的（就像它们在 $K$ 中一样），并且几乎翻转路径末尾的节点具有具有翻转提案的邻居，几乎翻转路径上的最后一个节点必须位于 $K\setminus B$ 中。

仅当 $c_v\in \{r,b\}$ 时，提案 $c_v$ 才会在一条链中被接受并在另一条链中被拒绝。 在这种情况下，路径末端具有相同颜色的链将拒绝，另一个将（可能）接受。 ∎

图2： 左侧的翻转路径：$v$ 的翻转提案在两个链中均被接受，产生 $X_v^{\prime }=r$ 和 $Y_v^{\prime }=b$。

右侧几乎翻转的路径：$v\in K\setminus B$对其提案进行一致采样。 在链$X$中，提案$r$将被接受，在链$Y$中，它将被拒绝，导致$X_v^{\prime }=r\ne Y_v^{\prime }=Y_v$。 磁盘颜色对应于节点的当前颜色，其中黑色表示除红色和蓝色之外的任何颜色。 节点周围方框的颜色表示该节点建议的颜色，其中白色表示任何颜色（也可以是红色和蓝色，但一致）。

2.3 限制不同节点的预期数量

我们通过分别限制期望 $𝔼[{\sum }_{v\ne v_0\in V}1\left(X_v^{\prime }\ne Y_v^{\prime }\right)\mid X,Y]$ 和 $𝔼[1\left(X_{v_0}^{\prime }\ne Y_{v_0}^{\prime }\right)\mid X,Y]$ 来显示对于某些 的 $𝔼[\varphi (X^{\prime },Y^{\prime })\mid X,Y]\le 1-\delta$。 我们将看到，作为 $\delta \to 0$，这两项都可以以 $\approx \frac{1}{\alpha }$ 为界，导致预期数量大致为 $\frac{2}{\alpha }$，对于以下情况，该数量严格小于 1 $\alpha >2$。

节点$v\ne v_0$

Section 2.2，或者更准确地说，Lemmas 2.1和 2.2，表明在 $X^{\prime }$ 和 $Y^{\prime }$ 中具有不同颜色的节点（不同于 $v_0$）的数量可以由具有附加属性的（几乎）翻转路径的数量限定。 接下来我们将看到这种（几乎）翻转路径的预期数量可以表示为对各层深度求和的几何级数。

$G$ 中最多有 ${\mathrm{\Delta }}^{\mathrm{\ell }}$ 条长度为 $\mathrm{\ell }$ 的路径 $(v_0,\mathrm{\dots },v_{\mathrm{\ell }})$。此外，每个这样的路径都有概率 ${\left(2\gamma /q\right)}^{\mathrm{\ell }-1}\gamma /q$ 成为具有上述附加属性的翻转或几乎翻转路径，因为所有中间节点 $v_1,\mathrm{\dots },v_{\mathrm{\ell }-1}$ 需要标记自己并在$\{r,b\}$ 和 $v_{\mathrm{\ell }}$ 需要标记自身并按照 Lemmas0> 中指定的方式提出 $\{r,b\}$ 中的一种颜色 2.11> 和 2.2 请注意，$G$ 中的路径可以是翻转路径或几乎翻转路径，但不能同时是两者。 此外，观察节点$v_0$不需要被标记。 我们得到

$$𝔼\left[\sum _{v\ne v_0\in V}1(X_v^{\prime }\ne Y_v^{\prime })\right|X,Y]\le \sum _{\mathrm{\ell }=1}^{\mathrm{\infty }}{\mathrm{\Delta }}^{\mathrm{\ell }}\cdot {\left(\frac{2\gamma }{q}\right)}^{\mathrm{\ell }-1}\cdot \frac{\gamma }{q}=\frac{1}{2}\sum _{\mathrm{\ell }=1}^{\mathrm{\infty }}{\left(\frac{2\gamma \mathrm{\Delta }}{q}\right)}^{\mathrm{\ell }}\le \frac{\frac{\gamma \mathrm{\Delta }}{q}}{1-\frac{2\gamma \mathrm{\Delta }}{q}}.$$ (1)

节点$v_0$

仅当至少一个提案被接受时，链 $X^{\prime }$ 和 $Y^{\prime }$ 才能在节点 $v_0$ 上达成一致。 为此，需要对 $v_0$ 进行标记，并且其提案 $c_{v_0}=c_{v_0}^X=c_{v_0}^Y$ 需要与其邻居的所有最多 $\mathrm{\Delta }$ 个当前颜色不同，即 $c_v\notin {\bigcup }_{v\in N(v_0)}\{X_v\}$，发生的概率至少为$\gamma \left(1-\mathrm{\Delta }/q\right)$。 此外，$v_0$的邻居（如果标记）的建议需要避免$\{c_{v_0},r,b\}$中最多三种颜色，可能更少，这种情况发生的概率至少为$1-3\gamma /q$。 由此我们得到

$$𝔼\left[1\left(X_{v_0}^{\prime }\ne Y_{v_0}^{\prime }\right)\right]\le 1-\gamma \left(1-\frac{\mathrm{\Delta }}{q}\right){\left(1-\frac{3\gamma }{q}\right)}^{\mathrm{\Delta }}.$$ (2)

包起来

总的来说，结合 方程 1 和 2，我们得到

$𝔼[\varphi (X^{\prime },Y^{\prime })\mid X,Y]$ $\le 1-\gamma \left(1-{\displaystyle \frac{1}{\alpha }}\right)e^{-\frac{6\gamma }{\alpha }}+{\displaystyle \frac{\frac{\gamma }{\alpha }}{1-\frac{2\gamma }{\alpha }}}=1-\gamma e^{-\frac{6\gamma }{\alpha }}\left(1-{\displaystyle \frac{1}{\alpha }}\left(1+{\displaystyle \frac{e^{\frac{6\gamma }{\alpha }}}{1-\frac{2\gamma }{\alpha }}}\right)\right).$

对于足够小的 $\alpha >2$ 和 $\gamma :=\gamma (\alpha )$ ，这严格限制在上面的 1 范围内，其中隐藏常量取决于 $\alpha$ （但不取决于 $\mathrm{\Delta }$ 或 $n$)。