今天学了一下 Lovasz Local Lemma 的构造性证明，感觉算法流程和调整法很像。
这里毛估估写一点过程。以下内容是从俺的博客 https://www.cnblogs.com/cauchysheep/p/16587302.html 直接抄过来的。
LLL 证明
Lovasz-Local lemma: 有一堆事件，每个事件有标号 $X_i$。如果对任意 $i$, 记 $V_i$ 满足：删掉 $V_i$ 之后 $i$ 与剩余事件完全独立，且 $P(A_i) \le X_i \prod_{j\in V_i} (1-x_j)$, 则有至少 $\prod (1-X_i)$ 的概率所有事件均不发生。
证明：对每个集合 $A$ 和 $a\notin A$, 我们证明 $A\cup \{a\}$ 均不发生的概率至少为 $A$ 均不发生的概率乘以 $(1-x_a)$。对 $|A|$ 归纳。注意到 $A\cup \{a\}$ 均不发生的概率为 $A$ 不发生的概率减去 $A$ 不发生且 $a$ 发生的概率，后者不超过 $A \backslash V_a$ 均不发生且 $a$ 发生的概率。而 $A \backslash V_a$ 与 $a$ 独立，两概率可以直接相乘。
又由归纳假设 $A \backslash V_a$ 均不发生的概率除以 $A$ 均不发生的概率不超过 $1/\prod_{j\in V_a} (1-x_j)$，化简得证。
$k-SAT$ 构造性证明
考虑构造每个 Clause 与不超过 $2^{k-2}$ 个其余 Clause 相交的 $k$-SAT 的解。
考察一个操作 $f(A)$，效果为：经过一些处理，使得 Clause $A$ 从不满足变成满足，原先满足的仍然满足。 具体执行定义如下：首先我们重新随机 sample $A$ 涉及到的变量。而后当存在 $A$ 有交 (含 $A$ 自己) 的 Clause $B$ 未满足，我们递归调用 $f(B)$。
$f$ 的正确性显然成立，我们希望证明 $f$ 的执行时间。事实上，我们只需要说明：$f$ 的调用时间 $\ge 2\log m$ 的概率不超过 $O(1/m^2)$ （于是，可以在某次超过 $2\log m$次调用后完全从头再来）。考虑固定一棵（给定根）的调用树，大小为 $t$。我们声称：这棵调用树出现的概率不超过 $1/2^{kt}$。这是因为每当树上节点用过一些变量，这些变量会立即被sample成新的值，所以树上节点的事件是完全独立的。而大小为 $t$ 的调用树个数有界：因为每次只有最多 $2^{k-2}+1$ 个邻点可供选择；为了回溯，也只需记录这个点是不是当前子树最后一个点即可。因此方法数不超过 $(2(2^{k-2}+1))^t$。
于是，大概率从外部 $m$ 次 $f$ 的调用后，每次调用的时间均不超过 $m\log m$。于是我们可以在不超过 $O(m^2\log m)$ 的时间给出构造。
一般的 LLL 构造性证明
考虑如下设定: 每个事件与 $\Omega$ 中若干个变量相关，$\Omega$ 中的变量两两独立。
我们考虑如下算法：初始给 $\Omega$ 中的变量随机赋值。当有事件发生时，我们将该事件涉及的变量重新 sample，一直执行知道所有事件均不发生。
我们证明：事件 $i$ 被重新 sample 的期望次数不超过 $x_i/(1-x_i)$。证明如下：记 $a_i$ 为事件 $i$ 重新 sample 的期望次数。我们将事件 $i$ 的每次 sample charge 到最近一次涉及到其中变量的修改上。那么容易发现， $a_i\le P_i (1+a_i+\sum_{j\in V_i}a_j)$. 化简后只需证明 $1\ge \prod (1-x_j) + \sum_j x_j \sum_{k\ne j} (1-x_k)$，显然得证。
鄂公网安备 42010202000505 号