前置
先定义 \(\text{independent}\)。称两个事件 \(A\) 和 \(B\) 为 \(\text{independent}\) 的，\(\text{iff}\;\Pr[A]=\Pr[A|B]\)，即 \(A\) 的发生概率与 \(B\) 无关。 称 \(A\) 与 \(A_1,A_2,..,A_m\) 所有事件 \(\text{independent}\)，\(\displaystyle \text{iff}\;\forall_{B_i\in\{A_i,\overline{A_i}\}}\Pr[A|B_1\wedge B_2\wedge..\wedge B_m]=\Pr[A]\)，即 \(\Pr[A]\) 与 \(A_1,..,A_m\) 发生与否的任何情况均无关。
再定义 \(\text{Dependency Graph}\)。有 \(m\) 个事件 \(A_1,A_2,..,A_m\) 作为 \(m\) 个节点，定义 \(\Gamma(A_i)\) 为 \(A_i\) 在 \(\text{Dependency Graph}\) 中的相邻节点集合，满足 \(A_i\) 与 \(\Gamma(A_i)\) 以外的所有事件 \(\text{independent}\)，\(A_i\) 与 \(\Gamma(A_i)\) 中的点连边。注意 \(\Gamma(A_i)\) 不是唯一的，并且最小的 \(\Gamma(A_i)\) 也不是唯一的，\(\text{Dependency Graph}\) 中的边可能是有向边，不具有对称性。不过对于任意的事件 \(A_1,..,A_m\)，必然存在一种 \(\text{Dependency Graph}\) 构建方式，使得所有边均为无向边（待证）。
Lovász Local Lemma (LLL)
\(A_1,...,A_m\) 通过 \(\Gamma(\cdot)\) 定义了其上的 \(\text{Dependency Graph}\)
引理的对称形式：
\(p\overset{\Delta}{=} \max_i \Pr[A_i],\quad d\overset{\Delta}{=}\max_i|\Gamma(A_i)|\\\)
引理的非对称（原始）形式：
证明
先证明非对称形式。
\(\displaystyle \Pr\left[\bigwedge_{i=1}^m\overline{A_i}\right]=\prod_{i=1}^m \Pr\left[\overline{A_i}|\bigwedge_{j=i+1}^m\overline{A_j}\right]=\prod_{i=1}^m \left(1-\Pr\left[A_i|\bigwedge_{j=i+1}^m\overline{A_j}\right]\right)\)，于是证明 \(\displaystyle \Pr\left[A_i|\overline{A_{j_1}}\cdots\overline{A_{j_k}}\right]\leq \alpha_i\) 对任意 \(k\) 和 \(A_{j_1},..,A_{j_k}\) 成立即可。
考虑归纳，\(k=0\) 时 \(\Pr[A_i]\leq \alpha_i\) 显然成立，\(k>0\) 时假设命题对小于 \(k\) 的情况均成立。
不妨设 \(A_{j_1},...,A_{j_l}\in\Gamma(A_i)\)，\(A_{j_{l+1}},...,A_{j_k}\notin\Gamma(A_i)\)，\(l=0\) 时是 trivial 的，下设 \(l\geq 1\)：
于是 \(\Pr\left[A_i|\overline{A_{j_1}}\cdots\overline{A_{j_k}} \right]\leq \alpha_i\)，归纳证毕。
接下来考虑对称形式。
令 \(\displaystyle\alpha_1=\cdots=\alpha_m=\frac{1}{d+1}\)，\(\displaystyle\alpha_i\prod_{A_j\in\Gamma(A_i)}(1-\alpha_j)=\frac{(1-\frac{1}{d+1})^{|\Gamma(A_i)|}}{d+1} \geq \frac{1}{d+1}(1-\frac{1}{d+1})^d\geq \frac{1}{e(d+1)}\) ，所以若 \(\displaystyle p=\max_i\Pr(A_i)\leq \frac{1}{e(d+1)}\)，即 \(ep(d+1)\leq 1\)，则 \(\displaystyle\Pr\left[\bigwedge_{i=1}^m\overline{A_i}\right]>0\) 。
另外令 \(\alpha_1=\cdots=\alpha_m=1/2d\) 可以将条件调整为 \(4pd\leq 1\) 。
Constraint Satisfaction Problem (CSP)
\(\text{Lovász Local Lemma}\) 的一个较大的应用实例是 \(\text{Constraint Satisfaction Problem}\)
\(\text{CSP}\) 定义：有变量 \(x_1,...,x_n\in[q]\)，限制 \(C_1,...,C_m\)，每个 \(C_i\) 定义在一个变量的子集 \(\text{vbl}(C_i)\) 上：
一组 \({\bf{x}}\in [q]^n\) 若满足所有限制 \(C_1,...,C_m\)，则称之为一组 \(\text{CSP solution}\) 。
\(\text{CSP}\) 包含众多知名问题，如：\(k-SAT\)、（超）图染色、集合覆盖、顶点覆盖、独立集、匹配……
例如考虑超图染色问题（Hypergraph Coloring）：
\(k\) 阶超图 \(H=(V,E)\)，\(V\) 为顶点集，\(\displaystyle E\sube \binom{V}{k}\) 为超边集合，定义点的度数为 \(\# e\ni v,e\in E\)。现对 \(H\) 图 \(q\) 染色，使得不存在一条超边上的所有点同色。
设 \(A_i\) 为 \(e_i\) 所有点同色的事件，若 \(e_i\cap e_j\neq \empty\) 则 \(A_i\) 和 \(A_j\) 在 \(\text{Dependency Graph}\) 有边相连，设 \(\Delta\) 为 \(H\) 节点的最大度数。\(p=\Pr[A_i]=q^{1-k}\)，此时 \(d\leq k(\Delta-1)\)，根据 \(\text{LLL}\)，若 \(ep(d+1)=eq^{1-k}k(\Delta-1)\leq 1\)，则 \(\Pr\left[\bigwedge_{i=1}^m\overline{A_i}\right]>0\)，这意味着 \(H\) 至少存在一组合法的染色。
条件可以等价写成 \(\displaystyle\Delta\leq \frac{q^{k-1}}{ek}+1\) 或 \(k\geq \log_q\Delta+\log_q\log_q\Delta+O(1)\) 。
The Moser-Tardos Algorithm
（Tardos 是匈牙利语，发音为 Tardish）
以上关于 \(\text{LLL}\) 是存在性的证明，而 \(\text{The Moser-Tardos Algorithm}\) 给出了构造出一组解的算法：
\(\text{The Moser-Tardos Algorithm}\) 运行在 \(\text{CSP}\) 上，要求 \(x_1,...,x_n\) 为完全独立随机变量。
初始对 \(x_1,...,x_n\) 随机取样。
若存在一个 \(A_i\) 成立，重新随机所有变量 \(x_j\in\text{vbl}(A_i)\)
\(\text{Moser-Tardos}\) 在 2010 证明了以上算法在终止前期望进行不超过 \(\sum_{i=1}^m\frac{\alpha_i}{1-\alpha_i}\) 次重随机。
证明
-
定义 \(\Lambda\) 为 \(\text{M-T}\) 算法中每次重随机的事件 \(A_i\) 的序列：
\[\Lambda_1,\Lambda_2,\Lambda_3,...\in{\scr A} =\{A_1,...,A_m\} \] -
\(\text{Witness Tree}\) \(T(\Lambda,t)\) 是一棵有根树，每个节点 \(u\) 有标签 \(A_{[u]}\in\scr A\)
-
初始 \(T\) 有一个根节点，标签为 \(\Lambda_t\)
-
从 \(t-1\) 到 \(1\) 枚举 \(i\)：
若存在 \(u\in T\) 满足 \(\Lambda_i\in \Gamma^+(A_{[u]})\overset{\Delta}{=}\{A[u]\}\cup\Gamma(A_{[u]})\)
将节点 \(v\) 作为孩子接在最深的满足条件的 \(u\) 下边，标签为 \(\Lambda_i\)
-
最终得到 \(T(\Lambda,t)\)
定义 \({\scr T}_{A_i}\) 为以 \(A_i\) 为根的所有 \(\text{Witness Tree}\) 的集合。
-
-
（\(\text{Galton-Waston Process}\)）定义一棵以 \(A_i\) 为根的随机树 \(T_A\)：
-
初始 \(T_A\) 有一个根节点，标签为 \(A\)
-
从小到大枚举 \(i=1,2,...\)：
对于 \(T_A\) 上每个深度为 \(i\) 的节点 \(u\)
对于所有 \(A_j\in \Gamma^+(A_{[u]})\)，以 \(\alpha_j\) 的概率在 \(u\) 下边添加一个标签为 \(A_j\) 的孩子。
-
若深度没有增加，结束
-
现欲证 \(E(|\Lambda|)\leq\sum_{i=1}^m\frac{\alpha_i}{1-\alpha_i}\) 。
\(E(|\Lambda|)=\sum_{i=1}^mE(\#A_i)\)，下证 \(E_{\Lambda}(\# A_i)\leq\frac{\alpha_i}{1-\alpha_i}\) 。
\(\text{Lemma 1}\)：对于一棵 \(\text{Witness Tree}\;\tau\)，\(\displaystyle\Pr_{\Lambda}[\exists t,T(\Lambda,t)=\tau]\leq \prod_{u\in \tau}\Pr(A_{[u]})\)。
只需注意到对于一组时间序列 \(x_1,...,x_n\)，若 \(T(\Lambda,t)=\tau\)，则可同时满足 \(\forall u\in \tau,A_{[u]}\) 成立，而反之不亦然。在 \(T(\Lambda,t)\) 中，\(v\) 满足的是经 \(\text{dependent}\) 的父亲 \(u\) 满足的情形重随机后的情况。
\(\text{Lemma 2}\)：对于一棵特定的 \(\text{Witness Tree}\) \(\tau\in{\scr T}_{A_i}\)
在 \(\tau\) 上的一个节点 \(u\)，其孩子标签的集合 \(\text{son}(u)\sube \Gamma^+(A_{[u]})\)，记 \(\Gamma^+_0(A_{[u]})=\complement_{\Gamma^+(A_{[u]})}\text{son}(u)\)
\[\Pr[T_{A_i}=\tau]=\frac{1}{\alpha_i}\prod_{u\in\tau}\left[\alpha_{[u]}\prod_{A_j\in\Gamma^+_0(A_{[u]})}(1-\alpha_j) \right] =\frac{1}{\alpha_i}\prod_{u\in\tau}\left[\frac{\alpha_{[u]}}{1-\alpha_{[u]}}\prod_{A_j\in\Gamma^+(A_{[u]})}(1-\alpha_j) \right]\\ =\frac{1-\alpha_i}{\alpha_i}\prod_{u\in\tau}\left[\alpha_{[u]}\prod_{A_j\in\Gamma(A_{[u]})}(1-\alpha_j) \right] \]
所以
因此 \(\displaystyle E(|\Lambda|)=\sum_{i=1}^m\underset{\Lambda}{E}[\text{# of } A_i\text{ in } \Lambda]\leq \sum_{i=1}^m\frac{\alpha_i}{1-\alpha_i}\)。\(\square\)