Tao–Vu · 加性组合学 · 第 1 章 概率方法

1.5　Lovász 局部引理The Lovász local lemma

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

本节目标我们手里有一大堆“坏事件”\(A_1,A_2,\dots\)，每一件都不希望发生。我们想证明：存在一种可能，让所有坏事件同时都不发生，也就是它们的补事件 \(\bar A_i\) 同时成立的概率严格大于 \(0\)。如果这些事件彼此完全独立，这件事很容易。难点在于：当事件之间存在少量、局部的相互依赖时，能否仍保证这个概率为正？Lovász 局部引理给出了肯定的回答，并给出可操作的判据。

设 \((A_i)_{i\in V}\) 是某个概率空间中的一族有限多个事件；稍后我们会把指标集 \(V\) 看作一个图的顶点集。在许多场合，我们希望证明：补事件 \((\bar A_i)_{i\in V}\) 有机会同时成立，即 \[ P\!\left(\bigcap_{i\in V}\bar A_i\right)>0. \] 当 \(A_i\) 是我们想要避免的“坏事件”时，这一点尤为有用。

把抽象语言落地“坏事件”到底指什么？这里给一个具体场景帮助理解符号。 于是 \(P(\bigcap_i \bar A_i)>0\) 的意思是：随机赋值时，存在至少一种赋值能同时满足全部子句——这正是“解存在”的证明。

独立的情形：平凡

如果诸 \(A_i\) 是相互独立的，那么问题是平凡的，因为我们有 \[ P\!\left(\bigcap_{i\in V}\bar A_i\right)=\prod_{i\in V}P(\bar A_i)=\prod_{i\in V}\bigl(1-P(A_i)\bigr), \tag{1.30} \] 只要所有 \(P(A_i)\) 都严格小于 \(1\)，这个乘积就是正的。另一方面，相互独立是一个非常强的假设，在实际中很少成立。

  1. “相互独立”让我们能把联合概率拆成逐项相乘：\(P(\bar A_1\cap\bar A_2\cap\cdots)=P(\bar A_1)P(\bar A_2)\cdots\)。这是 (1.30) 的第一个等号。
  2. 每个补事件的概率是 \(P(\bar A_i)=1-P(A_i)\)。这是第二个等号。
  3. 只要每个坏事件都不是必然发生（即 \(P(A_i)<1\)），每个因子 \(1-P(A_i)\) 就为正，整个乘积为正。
  4. 结论：所有坏事件可以同时避开。但前提“相互独立”太苛刻——现实里的约束往往共用变量，因而彼此牵连。
独立时联合概率 = 各因子相乘，只要每个因子为正，整体就为正 \(1-P(A_1)\) × \(1-P(A_2)\) × \(\cdots\) × \(1-P(A_m)\) = \(>0\)
独立情形 (1.30)：每个 \(1-P(A_i)>0\)，乘积就为正。难的是不独立时还能不能保证为正。

人们可以期待：如果允许 \(A_i\) 之间存在足够“局部”的依赖，使得我们即便在已经对大部分事件 \(\bar A_j\) 取条件之后，仍能对 \(P(A_i)\) 保持良好的控制，那么类似 (1.30) 的结论或许依然成立。事实证明这确实可行，正如 Lovász 在 1975 年与 Erdős 合作的论文 [93] 中所证明的那样。我们给出该引理的一个现代版本如下。

引理 1.25（Lovász 局部引理）设 \(V\) 是一个有限集，对每个 \(i\in V\)，设 \(A_i\) 是一个概率事件。假设在顶点集 \(V\) 上存在一个有向图 \(G(V,E)\)（无自环），称为诸 \(A_i\) 的依赖图（dependency graph）；并且对每个 \(i\in V\) 存在一列数 \(0\le x_i<1\)，使得估计 \[ P\!\left(A_i \,\Big|\, \bigcap_{j\in S}\bar A_j\right)\le x_i\prod_{(i,j)\in E}(1-x_j) \tag{1.31} \] 对所有满足下述条件的情形都成立：\(i\in V\)；\(S\subseteq V\setminus\{i\}\) 使得 \(\bigcap_{j\in S}\bar A_j\) 具有非零概率，且对一切 \(j\in S\) 都有 \((i,j)\notin E\)。那么对任意不相交的 \(S,S'\subseteq V\)，我们有 \[ P\!\left(\bigcap_{i\in S}\bar A_i \,\Big|\, \bigcap_{i\in S'}\bar A_i\right)\ge\prod_{i\in S}(1-x_i)>0. \tag{1.32} \] 特别地，我们有 \[ P\!\left(\bigcap_{i\in V}\bar A_i\right)\ge\prod_{i\in V}(1-x_i)>0. \]
读懂条件 (1.31)它在说一句很具体的话：取定一个坏事件 \(A_i\)，再任取一批与 \(i\) 在依赖图中不相邻的其它事件 \(\bar A_j\)（\(j\in S\)）。即便已知这批补事件全部成立（取了条件），\(A_i\) 发生的概率仍然被一个固定的小量 \(x_i\prod_{(i,j)\in E}(1-x_j)\) 压住。直觉是：和 \(i\) 不相邻的事件“管不着” \(i\)，所以对它们取条件不会把 \(A_i\) 的概率抬高太多。这里的 \(x_i\) 是我们自己挑选的一组“预算参数”，挑得好就能让 (1.31) 成立。
依赖图 G：连边 (i,j)∈E 表示“可能相互依赖”；不连边表示“互不影响” \(A_i\) \(A_1\) \(A_2\) \(A_4\) \(A_3\) \(A_5\) \(A_i\) 的邻居是 \(A_1,A_2,A_3\)（蓝）；\(A_4,A_5\)（绿）与 \(A_i\) 不相邻，对它们取条件不会“抬高”\(A_i\) 的概率
依赖图的作用：连了边的才可能彼此牵连。条件 (1.31) 中要求 \(S\) 里全是和 \(i\) 不相邻的点（如上图的绿色点），就是为了让取条件后 \(A_i\) 仍可控。

图 \(G\) 通常被称为诸 \(A_i\) 的依赖图。注意，如果我们有 \[ P(A_i)\le x_i\prod_{(i,j)\in E}(1-x_j), \] 并且每个 \(A_i\) 与所有满足 \((i,j)\notin E\) 且 \(j\neq i\) 的 \(A_j\) 都相互独立，那么 (1.31) 就会成立。这其实正是该引理最初表述中所陈述的假设。然而，在某些场合，这类相当强的相互独立假设并不具备，这时就需要引理 1.25 的完整威力。Alon 与 Spencer 的著作 [12] 第 5 章包含了许多有趣的应用。

例：对称型 Lovász 局部引理（最常用的特例） 假设所有坏事件“地位相同”：每个 \(P(A_i)\le p\)，并且依赖图中每个顶点的出度都不超过 \(d\)（即每个 \(A_i\) 至多与 \(d\) 个其它事件相邻）。我们统一取 \(x_i=x\)。
  1. 此时 (1.31) 的充分条件 \(P(A_i)\le x_i\prod_{(i,j)\in E}(1-x_j)\) 变为 \[ p\le x(1-x)^d. \]
  2. 取 \(x=\dfrac{1}{d+1}\)，可以证明只要 \(e\,p\,(d+1)\le 1\)（这里 \(e=2.718\dots\)），上式就成立。
  3. 于是结论给出 \(\displaystyle P\!\left(\bigcap_i\bar A_i\right)\ge\Bigl(1-\tfrac{1}{d+1}\Bigr)^{m}>0\)，即所有坏事件可同时避免。
代入具体数字感受一下：设每个坏事件概率 \(p=0.05\)，每个事件至多与 \(d=2\) 个事件相邻。取 \(x=\tfrac13\)，则 \(x(1-x)^d=\tfrac13\cdot\bigl(\tfrac23\bigr)^2=\tfrac{4}{27}\approx0.148\ge0.05=p\)，条件满足。于是无论有多少个这样的事件，都能保证它们全部被避开的概率为正。

引理的证明

引理 1.25 的证明. 我们对总基数 \(|S|+|S'|\) 作归纳。

若 \(|S|+|S'|=0\)，则 \(S,S'\) 均为空集，断言 (1.32) 平凡成立（空交事件取概率约定为 \(1\)，空乘积约定为 \(1\)）。现在归纳地假设 \(|S|+|S'|\ge 1\)，且断言对所有更小的 \(|S|+|S'|\) 值已经证明。

注意 \(|S|=0\) 的情形是平凡的（此时左边为对空集取交，概率为 \(1\)，右边空乘积为 \(1\)）。为对 \(|S|\ge 1\) 建立断言，只需对 \(|S|=1\) 的情形建立它即可。

事实上，若 \(|S|\ge 1\)，则可取某个 \(j\in S\)，把 \(S\) 拆分为 \(S=\{j\}\cup(S\setminus\{j\})\)。由条件概率的定义，我们有 \[ P\!\left(\bigcap_{i\in S}\bar A_i \,\Big|\, \bigcap_{i\in S'}\bar A_i\right) = P\!\left(\bar A_j \,\Big|\, \bigcap_{i\in S'\cup S\setminus\{j\}}\bar A_i\right)\cdot P\!\left(\bigcap_{i\in S\setminus\{j\}}\bar A_i \,\Big|\, \bigcap_{i\in S'}\bar A_i\right), \] 于是对第二个因子应用归纳假设进行估计，断言 (1.32) 即可推出。♦

这一步在做什么（拆分的逻辑）上面的等式是“链式法则”——把求多个补事件同时成立的概率，拆成一个一个剥： \[ P(\bar A_{j_1}\cap\bar A_{j_2}\cap\cdots)=P(\bar A_{j_1}\mid\cdots)\cdot P(\bar A_{j_2}\cap\cdots). \] 本证明每次从 \(S\) 中剥下一个事件 \(\bar A_j\)（这把 \(|S|\) 降了 \(1\)，所以可用归纳假设处理剩下的“第二个因子”），从而把一般情形化归到只剩一个事件、即 \(|S|=1\) 的核心情形。下面把那一步核心情形补全。
证明续：核心的 \(|S|=1\) 情形（本节 PDF 在此处截止，以下补全这一标准论证） 现在只需证明：对任意 \(i\) 与不含 \(i\) 的 \(S'\)，有 \(P\!\left(\bar A_i\mid\bigcap_{j\in S'}\bar A_j\right)\ge 1-x_i\)，等价地 \(P\!\left(A_i\mid\bigcap_{j\in S'}\bar A_j\right)\le x_i\)。
  1. 把条件集 \(S'\) 按与 \(i\) 是否相邻拆成两部分： \[ S_1=\{\,j\in S':(i,j)\in E\,\}\ (\text{邻居}),\qquad S_2=S'\setminus S_1\ (\text{非邻居}). \]
  2. 用条件概率定义把目标量写成分式： \[ P\!\left(A_i\,\Big|\,\bigcap_{j\in S'}\bar A_j\right) =\frac{P\!\left(A_i\cap\bigcap_{j\in S_1}\bar A_j\,\Big|\,\bigcap_{j\in S_2}\bar A_j\right)} {P\!\left(\bigcap_{j\in S_1}\bar A_j\,\Big|\,\bigcap_{j\in S_2}\bar A_j\right)}. \]
  3. 估分子（往上压）：丢掉 \(\bigcap_{j\in S_1}\bar A_j\) 这一交集只会让概率不增，再用 (1.31)（注意 \(S_2\) 全是 \(i\) 的非邻居，正合 (1.31) 的适用前提）： \[ \text{分子}\le P\!\left(A_i\,\Big|\,\bigcap_{j\in S_2}\bar A_j\right)\le x_i\prod_{(i,j)\in E}(1-x_j). \]
  4. 估分母（往下托）：对 \(S_1\)（其基数小于原 \(|S|+|S'|\)）用归纳假设 (1.32)： \[ \text{分母}=P\!\left(\bigcap_{j\in S_1}\bar A_j\,\Big|\,\bigcap_{j\in S_2}\bar A_j\right)\ge\prod_{j\in S_1}(1-x_j)\ge\prod_{(i,j)\in E}(1-x_j). \] （最后一步因为 \(S_1\) 中的点都是 \(i\) 的邻居，是 \(i\) 全体邻居的子集，而每个因子 \(1-x_j\le 1\)，乘的项越多积越小。）
  5. 相除：分子的上界除以分母的下界，\(\prod_{(i,j)\in E}(1-x_j)\) 上下抵消，得 \[ P\!\left(A_i\,\Big|\,\bigcap_{j\in S'}\bar A_j\right)\le\frac{x_i\prod_{(i,j)\in E}(1-x_j)}{\prod_{(i,j)\in E}(1-x_j)}=x_i. \]
  6. 因此 \(P\!\left(\bar A_i\mid\bigcap_{j\in S'}\bar A_j\right)=1-P\!\left(A_i\mid\bigcap_{j\in S'}\bar A_j\right)\ge 1-x_i\)，这正是 \(|S|=1\) 时的 (1.32)。归纳完成。♦
证明核心：把条件集 S' 切成“邻居 S₁”与“非邻居 S₂” \(A_i\) \(S_1\)：与 \(i\) 相邻 \(S_2\)：与 \(i\) 不相邻 无连边 → (1.31) 适用 连边 → 用归纳假设托住分母
关键的“分子往上压、分母往下托”：对非邻居 \(S_2\) 取条件后用判据 (1.31) 控制分子；邻居 \(S_1\) 那部分用归纳假设 (1.32) 控制分母，两边的 \(\prod_{(i,j)\in E}(1-x_j)\) 恰好抵消，留下 \(\le x_i\)。
即时自测
  1. 若所有 \(A_i\) 相互独立、且每个 \(P(A_i)=0.1\)，共 \(m=5\) 个，求 \(P(\bigcap_i\bar A_i)\) 的确切值，并验证它是否 \(>0\)。
  2. 在对称型特例中取 \(p=0.02,\ d=3\)。先验证 \(e\,p\,(d+1)\le 1\) 是否成立；再取 \(x=\tfrac1{d+1}=\tfrac14\)，检验 \(p\le x(1-x)^d\) 是否成立。
  3. 在证明的拆分式中，为什么必须把剥下的事件放在第一个因子、而把 \(S\setminus\{j\}\) 留给第二个因子才能用归纳假设？（提示：比较两个因子各自的 \(|S|+|S'|\)。）

返回 全书目录