Moser Tardos Algo

对于一系列的坏事件 \(\{A_1,\cdots,A_n\}\)，Lovász Local Lemma 指出，有可能使得所有的坏事件都不发生.

Moser Tardos Algorithm 是对这个定理的一个构造性证明.

Lovász Local Lemma

Let \(\mathcal{A}\) be a finite set of events in a probability space. For \(A\in \mathcal{A}\), let \(\Gamma(A)\) be a subset of \(\mathcal{A}\) satisfying that \(A\) is independent from the collection of events \(\mathcal{A}\backslash (\{A\}\cup \Gamma(A))\). If there exists an assignment of reals \(x: \mathcal{A}\to(0, 1)\) such that

\[\forall A\in \mathcal{A} : \mathbb{P}[A]\le x(A)\prod_{B\in \Gamma(A)}(1 - x(B)),\]

then the probability of avoiding all events in \(\mathcal{A}\) is at least

\[\prod_{A\in\mathcal{A}}(1-x(A))>0.\]

Moser Tardos Algorithm

首先定义 \(\mathcal{P}\) 是给定概率空间 \(\Omega\) 上有限个相互独立的随机变量的集合. 我们可以找到一个唯一的最小集合 \(S\subseteq\mathcal{P}\) 决定了 \(A\). 对于 \(S\) 中变量的一次 evaluation，假如它使得 \(A\) 发生了，我们就称 \(S\) violates \(A\). 这个集合 \(S\) 记作 \(\mathrm{vbl}(A)\).

假设 \(\mathcal{A}\) 是被 \(\mathcal{P}\) 决定的事件的集合. 我们可以定义 dependency graph \(G=G_{\mathcal{A}}\)，其节点是 \(\mathcal{A}\) 中的事件，两个节点 \(A, B\) 连边当且仅当 \(\mathrm{vbl}(A)\cap \mathrm{vbl}(B)\neq \varnothing\). 从而，\(\Gamma(A)\) 就是 \(A\) 的所有邻居的集合.

Algorithm

Sequential Solver

首先对 \(\mathcal{P}\) 中所有的 \(P\) 进行 evaluation，得到 \(v_P\).

接下来重复下面的循环：只要存在某个事件被这一组 \(v_P\) violate, 我们就从所有被 violate 的事件中随机抽取一个 \(A\)，对 \(\mathrm{vbl}(A)\) 中的所有的 \(P\) ，我们进行一次新的 evaluation. 最后返回这些 \(v_P\) 的值即可.

Theorem 1

在

\[\forall A\in \mathcal{A} : \mathbb{P}[A]\le x(A)\prod_{B\in \Gamma(A)}(1 - x(B))\]

的条件下，上面的随机化算法对事件 \(A\) resample 的次数的期望不超过 \(x(A)/(1-x(A))\). 于是，resampling 的次数的期望不会超过

\[\sum_{A\in \mathcal{A}}\dfrac{x(A)}{1-x(A)}.\]

Parallel Solver

上面的算法可以被并行化. 之前我们每次任意选取一个被 violate 的事件 \(A\). 现在我们考虑从所有被 violate 的事件出发 span 而成的 \(G_{\mathcal{A}}\) 的子图，选取其最大独立集（即图中两两不相邻的顶点的集合），对于这个独立集中的所有事件 \(A\) 的 \(\mathrm{vbl}(A)\) 进行 resample 即可.

Theorem 2

在

\[\forall A\in \mathcal{A} : \mathbb{P}[A]\le (1-\varepsilon) x(A)\prod_{B\in \Gamma(A)}(1 - x(B))\]

的条件下，上面的随机算法的步数的期望不超过

\[O\left(\dfrac{1}{\varepsilon}\log \sum_{A\in\mathcal{A}}\dfrac{x(A)}{1-x(A)}\right)\]

References

A Constructive Proof of the General Lovász Local Lemma

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在协议之条款下提供，附加条款亦可能应用