Moser–Tardos 重采样算法

形式陈述

设 $P_1,\ldots,P_n$ 是有限个相互独立的随机变量， $\mathcal A$ 是有限个可检测的坏事件。每个事件 $A$ 只由一个已知变量集合 $\operatorname{vbl}(A)$ 决定，记 $p_A=\Pr(A)$ 。两个不同事件的变量集合相交时连边， $\Gamma(A)$ 表示 $A$ 的邻居， $\Gamma^+(A)=\Gamma(A)\cup\{A\}$ 。这给出了Lovász 局部引理所需的依赖图，也给算法提供了具体的局部操作对象。

假设存在数 $0<x_A<1$ ，使每个事件满足

p_A\le x_A\prod_{B\in\Gamma(A)}(1-x_B).

先把全部变量按各自分布独立抽样一次。只要还有坏事件，就选择一个当前发生的事件 $A$ ，把 $\operatorname{vbl}(A)$ 中的全部变量独立重新抽样；其余变量保持原值。选择规则可以固定为“编号最小的坏事件”，也可以依赖目前已经观察到的历史，但不能预知尚未使用的随机数。

令 $N_A$ 为 $A$ 被重采样的次数， $R=\sum_A N_A$ 为总重采样次数。Moser–Tardos 定理给出

\mathbb E N_A\le\frac{x_A}{1-x_A}, \qquad \mathbb E R\le\sum_{A\in\mathcal A}\frac{x_A}{1-x_A}.

这里的期望只平均算法的抽样；输入事件族保持固定。初始化赋值不计入 $R$ 。右侧有限，因此算法以概率一终止，返回时所有坏事件均不发生。这个结论首先控制重采样次数；实际运行时间还取决于抽样、事件检测和寻找下一个坏事件的成本。

直觉

修复一个坏事件可能破坏邻居，因而坏事件数不必逐步减少。算法的进展不能靠“每次修复都更接近答案”来证明。真正可控制的是一段长期执行留下的依赖记录：某个事件再次发生，往往与此前修改过相同变量的修复有关。把这些历史倒着收集，就得到一棵见证树。树越大，需要同时满足的独立随机条件越多；局部引理的权重恰好足以支付所有可能树的总和。

把随机性预先放进表里

为每个变量 $P$ 准备一行独立样本

T(P,0),T(P,1),T(P,2),\ldots.

同行各格都服从 $P$ 的原分布，所有表格单元相互独立。初始化使用第 $0$ 列。变量 $P$ 已被重采样 $r$ 次时，其当前值就是 $T(P,r)$ ；下一次重采样把它换成 $T(P,r+1)$ 。固定整张表与选择规则后，整个算法成为确定过程。这是随机化算法的随机带观点，只是把随机带按变量分行。

把重采样日志记为 $A_1,A_2,\ldots$ 。日志中的 $A_t$ 表示第 $t$ 次重采样的事件，它在这次重采样之前的状态中发生。证明检查的正是这个旧状态，而不是此次修复刚抽出的新值。

从末步倒读出见证树

固定一次重采样 $t$ ，先建立标签为 $A_t$ 的根。依次倒读 $A_{t-1},\ldots,A_1$ ：若该事件与树中任何节点的变量集合相交，就把新节点接到所有可接节点中深度最大的一个下面；并列时使用固定规则。若完全不相交，就跳过。这里深度、父节点等术语采用有根树的通常定义，根的深度为 $0$ 。

得到的树有两个性质。每个孩子的标签属于父标签的闭邻域 $\Gamma^+$ ，而同一父节点的孩子标签互异：若后加入的孩子与已有孩子同标签，它就能接到已有孩子下面，不会仍接在原父节点上。称满足这两个条件的树为 proper 见证树。实际日志产生的树还满足更强的性质：同一深度的两个节点不共享变量。因为新节点若与某个已有节点共享变量，最深挂接规则就使它的深度严格大于那个节点。

对事件 $A$ 的第 $j$ 次重采样，所得树恰含 $j$ 个标签为 $A$ 的节点：此前每次 $A$ 都与根相交，必被收进树。因此同一事件的不同重采样得到不同的树。这个事实把运行次数变成“有多少棵不同见证树出现”的计数。

一棵树出现的概率

先固定一棵能够由上述构造产生的树 $\tau$ 。对节点 $v$ 及其标签中的变量 $P$ ，定义

r_\tau(v,P) =\#\{u:\operatorname{depth}(u)>\operatorname{depth}(v),\quad P\in\operatorname{vbl}(\ell(u))\},

其中 $\ell(u)$ 是节点标签。用值 $T(P,r_\tau(v,P))$ 检查节点 $v$ 的事件是否发生。

为什么这正好是日志中该步修复前的值？在倒读扫描中，一旦 $v$ 被加入，所有比它更早、且重采样了 $P$ 的日志项都会与树相交，因而全部被收进树。每个这样的项都被挂到比已有所有含 $P$ 节点更深的位置。反过来，较晚的含 $P$ 项在扫描中先加入，深度都较浅。因此更深的含 $P$ 节点数，正好等于该步之前 $P$ 已被重采样的总次数，没有遗漏开头的历史。最早的含 $P$ 节点检查第 $0$ 列，紧接着的检查第 $1$ 列，依次类推。

同一变量在不同节点使用不同列，不同变量使用不同的行，所以各节点的检查依赖互不相交的独立表单元。每个节点通过检查的概率都是 $p_{\ell(v)}$ 。树若真的出现，所有检查必通过，故

\Pr[\tau\text{ 出现}] \le\prod_{v\in V(\tau)}p_{\ell(v)}.

这里没有把原执行中各次坏事件当成独立事件；独立的是固定树指定的表格单元。一般 proper 树未必满足同层变量不交，不能直接对它套用这段表格检查；但不可能出现的树，其出现概率为零，仍满足上界。于是下面可以对全部 proper 树求和，以较大的树族覆盖实际执行。

用分枝概率求和

固定根标签 $A$ ，另造一个辅助随机过程：根必定出生；对每个已出生节点 $v$ ，为 $\Gamma^+(\ell(v))$ 中每个标签 $B$ 独立掷一次硬币，以概率 $x_B$ 产生一个标签为 $B$ 的孩子。不同节点的硬币也相互独立。它恰好能产生所有有限 proper 树，并且可能永远生长。

记 $C(v)$ 为 $v$ 的孩子标签集合，令

q_B=x_B\prod_{D\in\Gamma(B)}(1-x_D).

产生某棵有限树 $\tau$ 后停止的概率为

\begin{aligned} b_\tau &=\prod_v\left( \prod_{B\in C(v)}x_B \prod_{B\in\Gamma^+(\ell(v))\setminus C(v)}(1-x_B) \right)\\ &=\left(\prod_{v\ne\mathrm{root}} \frac{x_{\ell(v)}}{1-x_{\ell(v)}}\right) \prod_v\prod_{B\in\Gamma^+(\ell(v))}(1-x_B)\\ &=\frac{1-x_A}{x_A}\prod_v q_{\ell(v)}. \end{aligned}

第二行把“出生”的因子写成替换“不出生”因子的比值；每个非根节点恰好贡献一次该比值。根没有被父节点抽中，因此最后保留系数 $(1-x_A)/x_A$ 。

令 $\mathcal T_A$ 为以 $A$ 为根的全部有限 proper 树。不同有限树是辅助过程互斥的最终结果，所以 $\sum_{\tau\in\mathcal T_A}b_\tau\le1$ ；不需要证明这个过程必定灭绝。由前面的树互异性、非负指标的期望求和及 $p_B\le q_B$ ，

\begin{aligned} \mathbb E N_A &\le\sum_{\tau\in\mathcal T_A}\Pr[\tau\text{ 出现}]\\ &\le\sum_{\tau\in\mathcal T_A}\prod_v p_{\ell(v)} \le\sum_{\tau\in\mathcal T_A}\prod_v q_{\ell(v)}\\ &=\frac{x_A}{1-x_A}\sum_{\tau\in\mathcal T_A}b_\tau \le\frac{x_A}{1-x_A}. \end{aligned}

这也完成了终止证明：若有正概率执行无穷次，非负随机变量 $R$ 的期望就不可能有限。

例子与边界

九个随机位的一次完整运行

取相互独立的公平位 $a,\ldots,i$ ，考虑三个CNF 子句

C_1=(a\lor b\lor c),\qquad C_2=(\neg a\lor d\lor e\lor f),\qquad C_3=(\neg b\lor g\lor h\lor i).

坏事件 $A_j$ 是 $C_j$ 不满足。依赖图为路径 $A_2-A_1-A_3$ ，边分别来自共享变量 $a,b$ ； $A_2,A_3$ 没有共享变量。因此 $p_1=1/8$ 、 $p_2=p_3=1/16$ 。选

x_1=\frac14,\qquad x_2=x_3=\frac18.

中心事件的条件右侧为 $(1/4)(7/8)^2=49/256\ge1/8$ ，两个叶事件的右侧均为 $(1/8)(3/4)=3/32\ge1/16$ 。定理给出

\mathbb E R\le\frac13+\frac17+\frac17=\frac{13}{21}.

下表展示一张可能的随机表产生的完整运行，位串按 $abcdefghi$ 排列，每次选择编号最小的坏事件。表中的坏事件集合针对该行状态重新计算。

刚完成的操作	当前九个位	当前坏事件	下一次重采样的变量
初始化	`000000000`	$\{A_1\}$	$a,b,c$
重采样 $A_1$	`110000000`	$\{A_2,A_3\}$	$a,d,e,f$
重采样 $A_2$	`010000000`	$\{A_3\}$	$b,g,h,i$
重采样 $A_3$	`000000000`	$\{A_1\}$	$a,b,c$
重采样 $A_1$	`001000000`	$\varnothing$	已终止

第一次修复使坏事件数从一变成二，第三次修复又回到初始赋值。这都不妨碍最后成功。四次重采样也不与小于一的期望上界矛盾：许多初始赋值根本不需要修复，一条较长轨迹不能代表平均值。

日志为 $(1,2,3,1)$ 。末次事件的见证树以最后的 $1$ 为根；倒读时先接入 $3$ ，再接入与 $3$ 不相交的 $2$ ，二者都成为根的孩子；最早的 $1$ 与这两个孩子均相交，在最深处并列时固定选择挂到 $2$ 下面。对变量 $a$ ，最深的 $1$ 、中间的 $2$ 、根的 $1$ 分别检查 $T(a,0),T(a,1),T(a,2)$ ；这些值依次为 $0,1,0$ 。对变量 $b$ ，相应的三个节点是最深的 $1$ 、孩子 $3$ 、根的 $1$ ，也分别检查第 $0,1,2$ 列。这显示树的深度控制的是各变量的历史用量，而非要求所有相关节点沿同一祖先链排列。

共享变量给出三事件依赖路径；日志按时间为一、二、三、一，末步见证树以最后的一为根，较早事件置于更深位置 — 依赖图与倒读日志得到的末步见证树

变量模型与几乎必然终止

抽象依赖图只说明哪些事件具有独立性关系，不会自动告诉我们怎样局部改变一个样本，同时保持其他变量原样。此算法要求明确的独立变量表示和重采样访问；一般概率空间中的局部引理不能仅凭依赖图直接调用它。即使这些条件齐备，“以概率一终止”也不等于每一张无限随机表都会终止，更不等于存在统一的确定步数上限。

推论与应用

从修复次数到 CNF 的实际成本

设 CNF 有 $n$ 个变量、 $m$ 个非空子句，总文字数为 $S$ 。先用 $O(n+S)$ 时间建立“变量 $\to$ 含它的子句”索引、初始赋值和坏子句集合。重采样子句 $i$ 后，遍历它所有变量的索引列表，收集并用时间戳数组去重受影响子句，再重新扫描这些子句的文字，更新坏子句集合。集合可用带位置索引的数组维护，使任选、加入和删除均为常数时间；证明不要求实现必须选择最小编号。

更具体地，设 $V_i$ 为子句 $i$ 的变量集， $I(P)$ 为含变量 $P$ 的子句列表。一次修复的工作量包括

O\!\left( |V_i|+ \sum_{P\in V_i}|I(P)|+ \sum_{j\in\Gamma^+(i)}|C_j| \right),

分别对应重采样、收集并去重、重新检查；这里假设公平位生成与单个文字求值为常数成本。若每个子句恰含 $k$ 个互异变量，依赖图最大度为 $d$ ，每个 $I(P)$ 至多含 $d+1$ 个子句，故单次成本为 $O(k(d+1))$ 。无需预先构造全部依赖边；显式建图的成本不能无根据地写成 $O(S)$ 。期望总时间于是为

O\!\left(n+S+k(d+1) \sum_{i=1}^m\frac{x_i}{1-x_i}\right).

局部引理页的 $k=8,L=10$ 例子有 $d\le72$ 。取统一权重 $x=1/73$ ，则 $x(1-x)^{72}\ge1/(73e)>1/256$ ，得到 $\mathbb ER\le m/72$ ；每次至多复查 $73$ 个长度为 $8$ 的子句。在上述索引实现中，期望时间为 $O(n+S+m)$ 。这是把具体参数代入后的时间保证。对一般事件系统，还需给出抽样与检测成本，并控制权重接近 $1$ 时增长的 $x_A/(1-x_A)$ ，才能声称多项式时间。

在这些成本条件下，算法是 Las Vegas 算法：返回的赋值总是满足全部子句，随机性决定为找到它需要修复多少次。见证树的作用，是把反复破坏与修复的执行轨迹，转化为可以逐项计量的概率对象。

参考资料

Robin A. Moser 与 Gábor Tardos，A constructive proof of the general Lovász Local Lemma，arXiv:0903.0544v3，2009-05-20，Algorithm 1.1、Theorem 1.2、§2 的见证树与重采样表、§3 的分枝过程求和。本文的算法与期望界以这一版本为准。
Chihao Zhang 课程，Advanced Algorithms, Lecture 11，2020-11-16，§§2.1–2.5：SAT 模型与见证树的教学展开；学生记录讲义，作为辅助阅读。

形式陈述 ​

把随机性预先放进表里 ​

从末步倒读出见证树 ​

一棵树出现的概率 ​

用分枝概率求和 ​

九个随机位的一次完整运行 ​

变量模型与几乎必然终止 ​

从修复次数到 CNF 的实际成本 ​

反向链接