动机
一阶矩论证控制的是坏事件概率之和。当事件数量很多时,这种方法可能失效,即使每个事件只与少数其他事件相互作用。局部依赖提供了另一条途径,用来证明所有坏事件可以同时避免。
证明所需要的不只是两两独立。对若干个各自互不相关的事件同时取条件,可能揭示出任何单个事件对中都看不到的信息。因此,依赖图所编码的是:一个事件与由全体非邻点构成的整个集合相互独立,而对条件概率做归纳,正是使这个集合变得可处理的办法。
本节证明有限局部引理的一般假设形式,也证明一个方便的对称特例,并给出完整的着色与子句应用。这是一个存在性定理;若要得到快速的构造性重采样算法,还需要额外的结果,不能仅凭正概率推出。
定义
定义 2.3.1
(坏事件与依赖图)
设 是有限概率空间中的事件。依赖图是定义在这些事件下标上的简单图,使得每个事件 都与由所有下标既不是 也不是 的邻点的事件所生成的 -代数相互独立。
因此,对于由这些非邻点事件及其补事件构成的任意联合条件,只要该条件的概率为正, 在此条件下就保持其原有概率。对每个事件分别两两独立是更弱的要求,并不是这里所用的定义。用 表示邻点集合。
对下标集合 ,回避指事件 ;当 为空集时,其概率为一。只有在已证明条件事件的概率为正之后,才使用相应的条件概率。
一种有用的构造从相互独立的基础变量出发。如果事件 只依赖于其中的一组变量,那么只要两个事件下标对应的变量集合有重叠,就在它们之间连边。非邻点事件联合起来只依赖于 的变量集合之外的变量;基础变量组之间的独立性恰好给出所需的 -代数独立性。
有限的 -一致超图是由 元顶点子集构成的族。这里的合规二着色指没有任何超边是单色的。对于 -CNF 的应用,每个子句使用 个互不相同的变量,每个变量恰有一个文字,且不含互反的重言文字对。
定理/命题
定理 2.3.2
(非对称有限局部引理)
设数 满足
对每个 成立。则
更一般地,对每个下标 以及不含 的集合 ,有
此断言中出现的所有条件事件,其概率为正均属于定理结论的一部分。
推论 2.3.3
(一个对称的局部依赖判据)
如果依赖图的最大度至多为 ,每个坏事件的概率至多为 ,并且
则同时回避所有坏事件的概率为正。这里 是通常的指数常数。当 时,充分条件就是 ,并且联合独立性给出各个回避概率的乘积。
推论 2.3.4
(稀疏重叠保证着色与满足赋值的存在)
设 -一致超图满足 ,且每条边至多与 条其他边相交。当 时,该超图存在无单色边的二着色。如果每个顶点至多属于 条边,则取 即可。
每个变量至多出现在 个子句中的 -CNF 公式,只要
就是可满足的。
零重叠的情形沿用前面独立事件的约定。这些只是充分条件,并不能刻画所有可着色的超图或所有可满足的公式。
证明思路或证明
先对条件坏事件概率做归纳界定,再做乘积
证明
(对条件集合作归纳得到条件回避界)
我们对 的大小作归纳来证明条件界,同时证明所有回避条件的概率为正。当 时,所假设的概率不等式至多为 ,因为乘积中的每个因子都至多为一。
假设对大小小于 的条件集合,条件界已经证明。大小至多为 的任意集合,其回避概率为正:把它的下标按任意顺序排列,用链式法则分解其回避概率。每个相继的因子至少为相应下标的 ,所用的条件集合大小至多为 。它们的乘积为正。
现在取 ,并把它分为 与 。第二个集合只含非邻点。如果第一个集合为空,则由依赖独立性得到原来的概率,它已经至多为 。
否则,先对回避 取条件,得到
由依赖性假设,分子等于 。通过给 排序来分解分母。每个条件回避因子的条件集合由 与 中靠前的一个真子部分组成,其大小至多为 。因此,由归纳假设,它被相应的 从下方界定。
于是
这就证明了下一层条件界。同样的链式法则论证随后给出大小为 的回避集合的概率为正。归纳可到达每一个有限集合,所以计算中没有对概率为零的事件取条件。
最后,把全部 个事件排序,并分解完整的回避概率。其各因子至少为相应的 ,由此得到定理中乘积为正的下界。当没有事件时,空乘积为一,与同一结论一致。
证明透视
归纳控制的是邻点条件所产生的分母
关键的一步是证明比所求更多的东西:对每个条件集合都有条件界,而不只是最后的乘积。单有乘积界并不能归纳,条件界却可以直接供链式法则使用。
此后每个假设各有一项任务。依赖图只用于分子,而且必须是联合的 -代数形式,因为回避 是对许多非邻点的联合条件。归纳假设只用于分母,条件集合大小至多为 ;正是在这里,邻点的回避可能降低概率。最后一个不等式丢掉了 以外邻点的因子 ;这些余量正是假设要带上完整邻点乘积的原因。每一层都先证明概率为正,下一层才作除法,逻辑次序因此成立。
对有界度选取同一个参数
证明
(以同一个参数得到对称判据)
当 时,取每个 。至多有 个邻点的顶点满足
最后的严格比较就是 ,它来自 ,后者可通过在 上对 积分得到。因此,对 所述的非严格上界已经足够。非对称引理适用,并给出回避概率为正。
当 时,每个事件与所有其他事件联合独立。分解回避概率恰好得到 ,只要每个概率都小于一,它就为正。
公式 在 时给出 ,超出了引理的参数范围;这正是要把这一边界情形单独说明的原因。
独立的基础选择验证的是所需的图,而不仅仅是两两计数
证明
(着色与满足赋值)
对超图的每个顶点独立且均匀地从两种颜色中取色。某条 元边为单色的事件概率为 。它的基础变量是其 个顶点的颜色。不相交的超边使用不相交的基础变量集合,而所有非邻点事件合起来仍然只使用该边之外的顶点颜色。因此,相交图是一个有效的依赖图。
如果每个顶点至多属于 条超边,则一条边的 个顶点中,每个顶点至多把它与另外 条边相连。重复计数只会高估,所以 是成立的。应用对称判据,即得到一个回避所有单色边事件的着色。
对于子句,独立且公平地为所有布尔(Boole)变量赋值。含 个互不相同变量的子句,恰在其 种赋值中的一种上为假,概率为 。让共享变量的子句相连。同样的分组独立性论证验证这是一个依赖图,度至多为 。回避所有子句为假的事件,恰好就是一个满足赋值,这就证明了第二个应用。
不同子句中文字符号相反并不会使这个图失效:依赖性由共享的基础变量决定,而不取决于文字的书写是否相同。变量互异与非重言的条件保证了所给出的子句概率;对其他子句化简则需要重新计算它们的参数。
存在性与高效构造仍是不同的问题
引理给出的正下界可能极小。即使是 个独立的公平比特坏事件,当每个事件都是其比特为零时,回避概率也是 。回避的赋值存在,但独立地整体重新采样直至成功,其期望试验次数为 。
因此,仅凭存在性定理并不能证明找到该对象的期望运行时间是多项式的。局部重采样定理也许可以利用更多结构,但它需要自己的算法、不变量与终止性分析。目前这些应用证明的是解存在,并没有给出未经陈述的高效搜索保证。
例题详解
例题 2.3.5
(十一致稀疏关联对任意多条边都成立)
设十一致超图的每个顶点至多位于十条边中。依赖度至多为 ,每个坏事件的概率为 。
利用 得 。无论边的总数是多少,合规的二着色都存在。而初等的一阶矩求和则要求边数小于 ,这说明了局部依赖为什么能超越那种全局检验。
例题 2.3.6
(变量出现次数有界保证八-CNF 有模型)
取每个子句含八个互不相同变量的子句,并设每个变量至多出现在十个子句中。每个失败概率为 ,依赖度至多为 。
充分表达式为 。因此该公式可满足,这里不需要对子句总数加以限制。如果数值检验失败,定理保持沉默,而不是证明不可满足。
例题 2.3.7
(非对称证书可用精确分数来检验)
取三个独立的有限选择,事件概率分别为 、、。以它们三个下标构成的路径是有效的依赖图;添加不必要的依赖边是允许的。取每个 。
端点的允许量是 ,超过 。中间的允许量是 ,超过 。因此回避概率至少为 。实际的独立回避概率是 ,这说明有效的证书不必是精确的。
概念视角组合
依赖界以局部相互作用取代坏事件的总数
该图并不声称事件之间相互独立。它标出了取条件可能起作用的位置,而参数 则为这种局部效应付出代价。独立的变量分组为该图提供依据;随后条件概率的归纳给出全局同时回避的结论。
常见错误
反例模式
两两独立并不能证明依赖图为空
设 是独立的公平比特。令 、、。每个事件的概率为二分之一,每一对的联合概率为四分之一。
然而回避 与 迫使 ,这使 发生,所以同时回避的概率为零。空的依赖图因而是无效的: 并不与由 和 构成的联合条件独立。两两的概率检验不能代替 -代数的假设。
其余两个错误涉及引理的参数及其结论的适用范围。
常见错误
(在度为零时代入 )
证明要除以 的乘积,所以需要 。在 时,统一的选取 等于一,引理不适用。这种情形要直接处理:联合独立性给出回避概率 ,当每个 时它为正。
常见错误
(把充分检验当作刻画或算法)
充分的数值检验没有逆命题:若 ,定理保持沉默,该实例仍可能可着色或可满足。检验成立证明的是存在性,而不是快速算法,因为所保证的概率可能小至 。
总结
依赖图提供了对非邻点的联合独立性。条件回避的归纳证明了非对称局部引理及其正的乘积界,随后取同一个 便得到有界度判据。稀疏重叠的着色与 SAT 问题由独立的基础变量推出,其概率、表示以及算法方面的局限都已明确。
练习
快速检查
(一个十二一致超图中每个顶点至多位于二十条边中。利用度界与 验证它可二着色。)
其单色事件的概率为 。
解答 · 答案
度至多为 。判据为 ,它小于 。因此存在回避所有单色边的二着色。该陈述并没有限制超边的总数,也没有提供多项式时间的搜索算法。
快速检查
(对每个变量至多出现在四个子句中的六-CNF 检验该充分判据。解释为什么对另一个公式此检验失败并不能证明其不可满足。)
使用共享变量的依赖图。
解答 · 答案
度界为 ,坏事件的概率为 。因此 ,证明了可满足性。判据失败只表示这一充分性定理不能确立模型的存在;可满足的实例可能含有许多相互依赖的子句或冗余的重复。
快速检查
(对双比特反例,列出四种结果以及各自发生的坏事件。验证两两独立性与同时回避的概率为零。)
在结果 时,三个事件全部发生。
解答
在 处,事件 全部发生。在 处只有 发生;在 处只有 发生;在 处只有 发生。每个事件占四种结果中的两种,每一对只在 处相交,概率为四分之一,等于它们边缘概率之积。
每种结果都有一个坏事件发生,所以不可能回避。尽管通过了每一项两两检验,空图仍不满足所需的联合独立性条件,这恰好就是证明中所用到的区别。