动机
当坏事件的概率之和小于 1 时,并集界(union bound)可以证明存在一个避开所有坏事件的结果。但当坏事件数量很多时,即使每个事件都很罕见、且只与少数其他事件相互作用,并集界也会失效。Lovász 局部引理(Lovász local lemma)利用这种稀疏的依赖结构,证明避开所有坏事件的结果依然存在。
该结论是存在性的。下面的证明并不提供寻找这个结果的高效算法。它还要求一个精确的依赖条件:分别与每个较远的事件两两独立,并不足以证明可以对这些事件的整体同时取条件。
定义
定义 6.5.1
(依赖图)
设 是概率空间中的事件。依赖图(dependency graph)是以事件下标为顶点的无向图,使得每个 都与由所有满足 且 不与 相邻的事件 所生成的联合 -代数相互独立。用 表示 的邻点集合。这种联合独立性意味着 与由这些非邻点事件所决定的任何事件都相互独立,其中包括它们的补事件之交。
对于相互独立的随机变量,依赖于互不相交的变量集合的事件是相互独立的。可以把变量集合有重叠的事件用边相连,从而得到一个有效的依赖图,即使其中某些被连接的事件恰好是相互独立的。允许多余的边存在,但这可能使所得的界变弱。
定理
定理 6.5.2
(一般局部引理)
设存在数 ,使得对每个 都有
则 。
定理 6.5.3
(对称局部引理)
若每个事件的概率至多为 ,依赖图的最大度至多为 ,且 ,则避开所有坏事件的概率为正。
证明:条件坏事件概率
证明
(对集合大小归纳证明条件坏事件概率)
我们先对 用归纳法证明:对每个下标 以及每个不含 的集合 ,都有
并且作为条件的事件具有正概率。空集的情形由假设直接得到,因为乘积至多为 1。对于一组被避开的事件,其交的正概率可这样得到:先把这些事件排序,再应用已经建立的条件概率上界,每一次继续避开一个事件的条件概率至少为 。
归纳步骤中,把 分为 与 。令 为下标属于 的所有事件都被避开这一事件, 为下标属于 的所有事件都被避开这一事件。由归纳假设,事件 具有正概率。由于 与其非邻点联合独立,故 。
将 的下标排序。由归纳假设,在以 以及避开 中较早的事件为条件时,下一个坏事件的概率至多为它对应的 。这里相关的条件集合不含这个下一个下标,且大小小于 。因此
现在有
最后一个不等式用到了假设,以及 是 的子集这一事实。归纳至此完成。最后,把全部 个坏事件排序,将相继的条件避开概率相乘,每一个都至少为 ,从而证明了一般引理。
证明透视
每个假设用在何处
证明用到三个假设,每个只在一个步骤中使用。 与其非邻居的联合独立性只用一次,即把 换成 ,其中 是 中所有事件的补事件之交。只有与其中每一个事件的两两独立并不足够,下面的反例会说明。归纳假设用于 中的邻居,所用的条件集合严格小于 ;这就是归纳对 进行的原因,也说明了为什么无须假设邻居之间如何相互依赖。数值假设在最后用来吸收分母:除以 至多损失不在 中的邻居所对应的因子,而这些因子都在 之内。
证明:对称判据
证明
(由一般引理推出对称判据)
对于 ,对每个 取 。由于每个顶点的度至多为 ,所以
最后一个不等式来自 。因此 蕴含一般引理的假设。当 时,这些坏事件在所需的意义下是联合独立的,每个事件的概率至多为 ;避开它们的概率是一些正因子的乘积。没有事件的情形是平凡成立的。
例题详解
例题 6.5.4
(一个稀疏的 3-CNF 公式)
考虑一个 3-CNF 公式,其中每个子句含有三个不同的变量,并且至多与另一个子句共享变量。在独立的公平随机赋值下,每个子句为假的概率是 。把共享变量的子句用边相连,得到的依赖图最大度 。由于 ,所以存在某个赋值使所有子句都被满足。
例题 6.5.5
(并集界可能太弱)
对于十个这样的子句,它们各自失败概率之和为 ,因此仅凭并集界无法给出全部被满足的概率的任何正下界。但如果上一个例子中的依赖条件成立,局部引理仍然保证存在一个满足所有子句的赋值。
例题 6.5.6
(独立事件)
设 100 个坏事件相互独立,每个的概率为 。它们的概率之和是 25,但避开所有这些事件的概率是 。此时依赖图的度为零,这说明事件的个数本身并不是真正的障碍。
例题 6.5.7
(检验一个不成立的判据)
若 且 ,则 。对称判据不适用。这一计算并不能证明无法避开所有事件;它只是说明这个充分性检验没有给出结论。
常见错误
反例模式
两两独立不等于联合独立
设 是两个独立的公平比特,令 。这三个比特两两独立,但 由数对 所决定。因此事件 分别与事件 和 独立,却不与它们的交相互独立。若仅凭两两独立就省去两条边,所得的依赖图并不满足上面的定义。
常见错误
(把依赖边当作实际存在的依赖)
依赖图中的一条边表示允许存在依赖,而不是说依赖必定发生。添加不必要的边仍然是有效的,但会增大度,并可能使对称不等式不再成立。反过来,省去一条边需要完整的联合独立性,而不仅仅是一个相关性的计算。
常见错误
(由存在性期望高概率或算法)
该引理保证的是正概率,因而是存在性。它并不说明均匀随机抽样得到的赋值会以高概率成功,本身也不能给出找到成功结果所需时间的界。构造性的版本需要额外的算法和假设。
谨慎地应用引理
首先明确概率空间和坏事件。然后计算或估计每个事件的概率。构造一个满足联合独立条件的图并估计其最大度;对于由独立变量定义的事件,变量集合互不相交可以方便地给出理由。最后检验数值不等式,并把对每个坏事件的避开转化回所要求的对象。
一个重复出现某个变量的子句,其失败概率可能不同于 。重言子句永远不会为假。该例假设三个变量互不相同,这样使子句为假所需的三个赋值就是三个独立的公平比特约束。依赖度是按与之至少共享一个变量的其他子句的个数来计算的,而不是按子句中变量的个数。
当某些事件的概率远小于其他事件,或邻点比其他事件更少时,非对称定理会很有用。它的参数 是逐个选取的,所以即使最坏情形下的单一 使对称判据失效,它仍可能成功。在每个应用中,选取这些参数并检验各乘积,仍然是证明的一部分。
超图染色的一个应用
设一个有限超图的每条边恰好含有 个不同的顶点,并且每条边至多与 条其他边相交。对每个顶点独立地以各一半的概率染成红色或蓝色。对于边 ,令 为其所有顶点颜色相同这一事件。在 种染色中有两种是单色的,所以 。
当两条超边相交时,把对应的坏事件相连。一个事件只依赖于它自己那条边的顶点颜色,并且与建立在互不相交的边上的事件所构成的整体相互独立。该依赖图的最大度至多为 。因此,只要
局部引理就给出一种没有单色边的染色。这是一个通常意义下的合适二染色,即每条超边都同时含有两种颜色。图中可以有很多条边;该条件控制的是局部的重叠,而不是坏事件的总数。
例如,若 且每条超边至多与另一条相交,则 ,并且 。于是存在合适的二染色。该结论并没有说明如何高效地找到它,也没有说明有多少种这样的染色。
一个非对称的计算
设有两个坏事件,由一条依赖边相连,其概率分别至多为 和 。取 ,。乘积条件为 以及 。一般引理给出避开概率至少为 。
仅对两个事件而言,并集界恰好给出更强的下界 。这个例子的目的是展示如何检验不相等的参数,而不是声称局部引理总能优于其他所有界。在更大的稀疏系统中,当事件概率之和超过 1 时,它的优势才会显现。
保证归纳是有据可依的
证明中的条件概率要求分母非零。在对集合 的归纳阶段,对每个更小集合,避开事件的正概率可由逐次补事件的已建立下界相乘得到。在分解 中,条件事件 具有正概率,而在 条件下 的乘积下界同样为正。因此 在作除法之前就具有正概率。
联合独立性假设只用于 ,而 是由 的邻域之外的事件所决定的。 中的事件可以任意地依赖于 以及彼此;归纳控制了它们的条件避开概率,而无需假设独立性。将这两种作用区分开来,可以避免把相邻事件的无条件避开概率直接相乘这一错误的捷径。
归纳中的条件概率不等式是有意取成单向的。在以 为条件的概率空间中,事件 是 的子集,所以它的概率至多为 。再除以 的正概率,就得到所示的上界。除非已知 与 之间有额外的关系,否则不能把这个不等式换成等式。
一般假设中的乘积取遍整个邻域,而归纳中只除以属于 的那些因子。每个因子都介于零和一之间,所以去掉一些因子会使乘积变大。因此该比值至多为 。局部的数值假设正是在这一点上吸收了因对邻近事件取条件而可能产生的损失。
正的下界可以极其微小。例如,许多小于 1 的因子之积,可能随事件个数增加而趋于零,尽管对每个固定的有限实例它都是正的。该定理适用于命题中所述的有限事件族;无限的版本需要另外的假设和论证。
对由独立变量决定的事件,简单的重抽样过程在期望意义下很快就找到。
自然的下一个问题
能高效地找出该结果吗?
对由独立变量决定的事件,简单的重抽样过程在期望意义下很快就找到。
对由独立随机变量决定的事件,重抽样过程有效:只要还有某个坏事件成立,就重抽该事件所涉及的变量。已知在与引理同类的条件下,它的期望重抽样次数是多项式的。其证明是另一种算法式论证,此处不给出。
总结
局部引理在依赖关系稀疏的情况下,仍能控制坏事件的条件概率。与非邻点的联合独立性以及乘积条件保证了相继避开每个事件时仍保持正概率。对称不等式给出一个方便的充分性检验,但并不提供搜索算法。
练习
快速检查
(对 和 计算 ,并判断对称检验是否适用。)
解答 · 答案
其值为 ,所以只要所述的依赖度和事件概率的界成立,该检验就保证避开所有事件的概率为正。
快速检查
(为什么在独立赋值下,变量集合互不相交的两个子句在依赖图中可以不相邻?)
解答 · 答案
每个子句为假的事件只依赖于该子句的变量。对互不相交的变量集合作独立赋值,使它与所有建立在其他互不相交的变量集合上的事件所构成的整体相互独立。
快速检查
(若局部引理的不等式成立,它的结论是什么:存在性、高概率,还是高效算法?)
解答 · 答案
它的结论是避开事件的概率为正,因此至少存在一个避开所有坏事件的结果。它本身并不保证高概率或高效搜索。
快速检查
(给出避开两个概率分别为 和 的独立坏事件的一个数值下界。)
解答 · 答案
由独立性,恰好有 。局部引理同样给出一个正的下界,但精确的独立性给出的是这个更精确的值。