Lovász Local Lemma

Introduction

我们希望研究，对于一系列的坏事件 \(\{A_1,\cdots,A_m\}\) ，有没有可能使得所有的坏事件都不发生. 即

\[\mathbb{P}\left[\bigcap_{i=1}^m \overline{A_i}\right]>0.\]

Symmetric LLL

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))\) and \(|\Gamma(A)|\le d\), i.e. the degree of the dependency graph is less than \(d\). If

\[\forall A\in \mathcal{A} : \mathbb{P}[A]\le \dfrac{1}{4d},\]

then the probability of avoiding all events in \(\mathcal{A}\) is greater than \(0\).

Asymmetric LLL

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

Moser Tardos Algorithm 是对 Lovász Local Lemma 的一个构造性证明.

首先定义 \(\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

假如事件集 \(\mathcal{A}\) 满足

\[\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

假如事件集 \(\mathcal{A}\) 满足

\[\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).\]

More Results

通过引入一些额外的限制，我们可以给出更紧的界.

Theorem 3

设 \(\mathcal{P}=\{P_1,\cdots,P_n\}\) 是有限个两两独立的随机变量的集合. 每个 \(P_i\) 从有限的值域 \(D_i\) 中取值. \(\mathcal{A}\) 是由 \(m\) 个事件构成的集合. 问题大小为 \(s=m+n+\sum |D_i|\) . 假定有一个算法，可以以关于 \(s\) 的多项式时间计算 \(\mathbb{P}[A\mid \forall i\in I: P_i=v_i]\) ，即可以计算在某组 evaluation 下 \(A\) 发生的概率. 同时假定 \(G\) 的最大度数不超过某个常数 \(k\)，即 \(\max |\Gamma(A)|\le k\) . 假如存在 \(\varepsilon>0\) 和 \(x:\mathcal{A}\to (0, 1)\) 满足

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

则存在以关于 \(s\) 的多项式时间求解上述问题的 deterministic algorithm.

Definitions

首先我们定义一些概念.

\(C:\mathbb{N}\to\mathcal{A}\) 是一个日志. 它记录了每次选择 resample 的事件. 例如 \(P,S,Q,R,P,\cdots\) .

\(\Gamma^+(A)=\{A\}\cup \Gamma(A)\) 是 \(A\) 的 inclusive neighbourhood.

\(\tau=(T,\sigma_T)\) 是一棵 witness tree. \(T\) 是一棵有限有根树. \(\sigma_T:V(T)\to \mathcal{A}\) 是 \(T\) 每一个节点的标号.

通过下面的过程，我们可以构建 witness tree \(\tau_C(t)\) :

首先，\(\tau_C^{(t)}(t)\) 是根节点 \(C(t)\) . 接着，对于 \(i=t-1,\cdots,1\) ，假如存在某个顶点 \(v\in\tau_C^{(i+1)}(t)\) 且 \(C(i)\in \Gamma^+([v])\) ，我们就选取所有的 \(v\) 中离根最远的（同深度随机选取），为它增加孩子 \(C(i)\) . 假如不存在这样的顶点，就不做修改.

用通俗的话来说：按照倒序考察日志 \(C(i)\) . 假如 \(C(i)\) 会被某个节点影响，就将它插入 \(\tau_C^{(i+1)}(t)\) 来得到 \(\tau_C^{(i)}(t)\) . 记 \(\tau_C(t)=\tau_C^{(1)}(t)\) ，我们就得到了从 \(t\) 步倒序构建出的 witness tree.

\(\tau_C(i)\) 共生成了 \(|C|\) 棵 witness tree. 对于这些 witness tree，我们说它们在日志 \(C\) 中出现.

假如 \(\tau\) 的每个节点的孩子具有不一样的标号，我们就称这样的 witness tree 是 proper 的.

Lemma 1

设 \(\tau\) 是一棵给定的 witness tree. \(C\) 是算法产生的随机日志.

假如 \(\tau\) 在 \(C\) 中出现，那么 \(\tau\) 是 proper 的，并且每一层是 \(G\) 中的一个独立集.
\(\tau\) 在 \(C\) 中出现的概率不超过 \(\prod\limits_{v\in V(\tau)}\mathbb{P}[[v]]\) .

记 \(N_A\) 为算法中 \(A\) resample 的次数，即 \(C(t)=A\) 的 \(t\) 的数量. \(t_i\) 为第 \(i\) 个满足 \(C(t)=A\) 的时间步，\(\mathcal{T}_A\) 为所有以 \(A\) 为根的 proper witness tree. 注意到 \(\tau_C(t_i)\) 中含 \(A\) 的个数恰好为 \(i\)，于是这些 witness tree 互不相同，于是

\[N_A=\sum_{\tau \in \mathcal{T}_A}1_{\tau \mathrm{\ occurs\ in\ } C}.\]

Random Generation

从一个根节点 \(A\) 出发，进行如下的随机生成：考虑上一轮后新增的顶点，对于每一个顶点 \(u\) ，考察 \(\Gamma^+([u])\) 中的所有顶点. 对于其中的顶点 \(v\) ，有 \(x(v)\) 的概率将其添加为 \(u\) 的孩子节点. 这一过程被称为 Galton-Watson process.

可以证明，对于某棵以 \(A\) 为根节点的 proper witness tree \(\tau\) , 其生成的概率是

\[p_\tau = \dfrac{1-x(A)}{x(A)}\prod_{u\in V(\tau)}x'([u])=\dfrac{1-x(A)}{x(A)}\prod_{u\in V(\tau)}x([u])\prod_{v\in \Gamma([u])}(1-x([v])).\]

通过这个结果，我们可以得到

\[\mathbb{E}(N_A)\le \dfrac{x(A)}{1-x(A)}.\]

Shearer's Lemma

上面的 Lovász Local Lemma 只是一个充分条件. 下面的 Tight Lovász Local Lemma (Shearer, 1985) 给出了使得所有坏事件都不发生的充分必要条件.

现在我们直接来考察 dependency graph \(G\) 和 \(\vec{p}=(p_1,\cdots,p_m)>0\).

Alternating sign independence polynomial:

\[\breve{q}_{S} = \sum_{I\in \mathrm{Ind},\ I\subseteq{S}}(-1)^{|I|}p^{I}=\sum_{I\in \mathrm{Ind},\ I\subseteq{S}}(-1)^{|I|}\prod_{i\in I}p_i.\]

An alterative form of the polynomial:

\[q_{I}=\sum_{J\in\mathrm{Ind},\ I\subseteq J}(-1)^{|J\backslash I|}p^{J}=\sum_{J\in\mathrm{Ind},\ I\subseteq J}(-1)^{|J\backslash I|}\prod_{j\in J}p_j.\]

Shearer's region:

\[\mathcal{S}=\{\vec{p}\in(0,1)^m: \forall S\subseteq[m], \breve{q}_S(p)>0\}=\{\vec{p}\in(0,1)^m: \forall I\in \mathrm{Ind}, q_I(p)>0\}.\]

Tight Lovász Local Lemma 指出，

\[\vec{p}\in \mathcal{S}\Leftrightarrow\mathbb{P}\left[\bigcap_{i=1}^m \overline{A_i}\right]>0.\]

当满足下面的条件时，上面的条件可以进一步增强，即假定存在相互独立的随机变量 \(\mathcal{P}\) 和被它们决定的事件集 \(\mathcal{A}\), 则

\[\vec{p}\in \mathcal{S}\Rightarrow\mathbb{P}\left[\bigcap_{i=1}^m \overline{A_i}\right]>0.\]

我们先来证明一个引理. 假如对于所有的 \(S\)，\(q_S\ge 0\)，则

\[\mathbb{P}\left[\bigcap_{i=1}^m \overline{A_i}\right]\ge q_{\varnothing}.\]

引理的证明

任取 \(G\) 中的一个独立集 \(R\)，注意到

\[\sum_{R\subseteq S}q_S=\sum_{R\subseteq S}\sum_{R\subseteq S\subseteq T,\ T\in \mathrm{Ind}}(-1)^{|T|-|S|}\prod_{j\in T}p_j=\sum_{R\subseteq T,\ T\in\mathrm{Ind}}(-1)^{|T|}\prod_{j\in T}p_j\sum_{R\subseteq S\subseteq T}(-1)^{|S|}=\prod_{j\in R}p_j.\]

于是 \(\sum_S q_S=1\). 从而可以构造概率分布.

假定 \(q_S\ge0\)，则 \(Y\) 是取值在 \(\{0,1\}^m\) 的随机变量，其概率为 \(q_Y\).

注意到如下的性质：如果我们写成 \(Y=\overline{Y_1Y_2\cdots Y_n}\)，则 \(Y_i=1\) 的概率为

\[\sum_{\{i\}\subseteq S}q_S=p_i.\]

同时，对于独立的 \(A_i, A_j\)，依据

\[\mathbb{P}[Y_i=1, Y_j=1]=p_ip_j=\mathbb{P}[Y_i=1]\mathbb{P}[Y_j=1],\]

于是 \(Y_i, Y_j\) 也是独立的. （论文中指出 \(Y_i\) 的 dependency graph 也是 \(G\)，为什么？）

例如，101110001 的概率是 \(q_{\{1,3,4,5,9\}}\)，其中 \(S=\{1,3,4,5,9\}\).

定义 \(\alpha(S)\) 是 \(S\) 中所有事件均不发生的概率，\(B(S)\) 是 \(Y\) 在 \(S\) 中的位置都是 \(0\) 的概率. 于是

\[B(S)=\sum_{S'\subseteq \bar{S}}q_{S'}=\sum_{S'\subseteq \bar{S}}\sum_{S'\subseteq T,\ T\in \mathrm{Ind}}(-1)^{|T|-|S'|}\prod_{j\in T}p_j=\sum_{T\in\mathrm{Ind}}(-1)^{|T|}\prod_{j\in T}p_j\left(\sum_{S'\subseteq T\cap \bar{S}}(-1)^{|S'|}\right)=\breve{q}_S.\]

由于 \(\alpha([n])\) 是所有坏事件均不发生的概率，\(B([n])=q_{\varnothing}\). 我们使用归纳法来证明下面的结论即可：

\[S_1\subseteq S_2\Rightarrow \dfrac{\alpha(S_1)}{B(S_1)}\le \dfrac{\alpha(S_2)}{B(S_2)}.\]

下面我们来探讨存在 \(q_S<0\) 的情形.

References

A Constructive Proof of the General Lovász Local Lemma

On a Problem of Spencer

计算理论之美 (Summer 2021)

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