动机
证明一个好的对象存在,不必总是直接构造它。可以先定义随机试验,证明结果质量的期望很高,再推出至少有一个好结果。条件期望法更进一步:逐个确定随机选择,同时保持最终质量的条件期望下界。我们用最大割说明这两个步骤,并区分概率论证和高效计算条件期望所需的算法工作。
定义
定义 6.6.1
(割、割重量与二分之一近似保证)
设 是有限无自环无向图,边权 都是非负实数。割是划分 ;边的端点属于不同部分时称该边跨越割。割的重量是所有跨越边的权重和。令 ,并令 为最大割重量。若随机算法对每个这样的输入都满足期望割重量至少为 ,称其期望近似比至少为 。期望针对固定图上的算法随机选择;它不保证每次运行达到该值。
定理/命题
定理 6.6.2
(随机割的期望)
每个顶点独立地以各 的概率放入两部分之一。所得割的期望重量为 ,而且至少存在一个重量不小于 的割。
定理 6.6.3
(条件期望构造)
存在确定性算法,逐个确定顶点所在侧而不降低最终割重量的条件期望,最终输出重量至少为 的割。
证明思路
证明
(对边指示变量使用期望的线性性)
对每条边 ,令指示变量 在两端位于不同侧时为 1,否则为 0。两端独立公平选择,故 。割重量为 ,期望线性性给出
期望线性性不要求所有边的指示变量联合独立。三角形中跨越边的条数必为偶数,所以三个指示变量不可能同时为 1;但每个变量为 1 的概率都是 。故三者同时为 1 的概率为零,而不是 。仅仅共享顶点并不能证明不独立:简单图中不同的两条边的指示变量在此公平选择实验下是独立的。独立性用于计算每条边自身跨越的概率。可能的割只有有限多个,其平均重量为 ,因此至少一个割的重量不低于平均值;否则平均值也会更低。
证明
(条件期望从不下降)
对于确定性构造,假设部分顶点的侧已固定,其余顶点仍独立公平选择。设当前条件期望为 ,未固定顶点 放入 、 后的条件期望分别为 。全期望公式给出 。两者至少有一个不小于 ;选择该侧并继续。所有顶点确定后,条件期望就是实际割重量。由于过程中从未下降,最终重量至少为初始值 。
条件值易于计算。两端均已确定的边,跨越时贡献全部权重,否则贡献零。至少一端未确定的边,其条件跨越概率为 ,贡献一半权重;这里使用剩余选择的独立公平性。因此可扫描关联边求出 ,算法是多项式时间。采用适当记录,固定两个端点时每条边只需常数次处理。
证明透视
为什么不变量不会下降
证明维持一个不变量:给定到目前为止已固定的侧,最终割重量的条件期望 不低于 。开始时什么都未固定,,不变量成立。唯一不寻常的一步,是 为 与 的平均:下一个顶点的公平选择独立于已固定的侧,各以概率 取两侧,所以两者中较大的一个不可能低于它们的平均值。这正是存在性证明中的平均论证,逐个决定地使用,也正是它把存在性变成一个过程。
结束时没有随机性剩下, 就是输出割的重量。不变量本身对权重没有任何假设;非负性只在把 与 比较时才用到。这个过程还需要 与 可以计算,上面的证明已经提供了这一点。
例题详解
例题 6.6.4
(三角形)
单位权重三角形有 ,随机割期望为 。将一个顶点放一侧、其余两个放另一侧,会跨越两条边,重量为 2,高于平均值。所有顶点放同一侧的结果重量为零,说明单次随机运行不一定达到期望。
例题 6.6.5
(根据条件期望选择)
设单位权重三角形的 已放在 , 尚未确定。若 放入 , 贡献零,而 各贡献 ,条件期望为 1。若 放入 , 贡献 1,另两条边各贡献 ,条件期望为 2。因此选 。无论 随后放在哪侧,最终重量都是 2。
例题 6.6.6
(不同权重)
三顶点路径的两条边权为 2 和 6,则 、随机割期望为 4。把中间顶点放一侧、两端放另一侧可跨越两条边,重量为 8。权重非负保证 ,这把 保证连接到 。
常见错误
常见错误
(平均值不是逐次运行的保证)
期望是平均值,不是逐次运行的保证。三角形的零重量结果反驳了“每个随机割至少为 ”。高平均值本身证明存在,却不自动提供高效的确定性搜索;上面的构造依赖条件期望能够高效计算。
反例模式
负权重使二分之一近似保证失效
一个诱人的说法是:无论权重如何,随机割的期望重量都至少为 。取两个顶点之间一条权重为 的边。此时 ,随机割的期望重量为 ,与线性性的预测一致。但把两个顶点放在同一侧,不跨越任何边,所以 ,而 ,上述说法不成立。
失效的是 这一步,它需要非负权重;这里 。对任意实权重, 的计算仍然成立,但其近似意义必须重新分析。
总结
随机选择给出平均值,平均值给出存在性。当下一步条件值可高效计算时,条件期望法将证明转化为构造。边指示变量不必彼此独立,但计算每条边的跨越概率使用了顶点的独立公平选择。
近似保证及其局限
每个割只使用边集的一个子集。权重非负时,其重量至多为 ,所以 。因此随机割的期望和确定性构造均满足
这是相对于可能难以高效计算的最优值的下界,并未断言 ;奇圈不可能每条边都跨越割。若 ,所有权重为零,每个割重量都为零,上述不等式仍成立。此时直接把两个数值重量相除没有定义,因此用不等式表述较稳妥。
对于一条权重为 1 的边,随机割的期望为 ,最优值为 1,因此这个随机试验的分析可以达到等号。条件期望法会把两端放在不同侧,在此例中达到最优,但这不证明它在每个图上都找到最优割。
概念视角代数
用正负号表示割的权重
用符号 表示顶点所在的一侧。边 被割开当且仅当 ,所以它的指示变量是 ,于是
对独立的公平符号,,由此再次得到 。要使割最大,就是要使带符号的和尽可能小(负得尽可能多)。对权重为 的一条边,,符号相反时等于 。
对于较低的门槛,可以得到概率保证。设 ,令 为未跨越边的总权重。权重非负给出 ,而 。马尔可夫(Markov)不等式给出
因此 。这比每次达到半最优的保证弱,却是真正的单次概率结论。它同样依赖非负权重和 。独立重复可提高至少一次超过 的概率;放大需要各次运行之间使用独立随机选择。
明确的条件更新
确定未赋值顶点 时,考虑一条权重为 的关联边 ,其中 已确定。在选择之前它贡献 的条件期望。把 放在 的对侧,贡献变为 ;放在同侧则变为零。若 的另一邻点尚未确定,不管如何选择 ,这条边仍贡献 ,因为邻点仍公平随机。与 不关联的边不变。因此较好的选择是跨越与已确定顶点相连边的总权重至少一半的那一侧。
例如, 已确定的邻点中,位于 的关联边总权重为 7,位于 的为 4。把 放入 就跨越前者的 7;放入 则跨越后者的 4。前者保持或增加条件期望。比较时只需要已固定的邻点;未来的边并没有被忽略,而是在两种选择下的条件贡献相同。
这一更新也具体说明运行时间。按固定次序处理顶点;每条边的第二个端点被处理时,查看第一个端点所在侧,并把该边权加入相应总和。在常见邻接表表示下,每个邻接项只访问常数次。在实数算术操作模型下,图操作和算术操作次数为 。若有理权重以比特编码,位复杂度还取决于其表示方式和算术成本。
平均论证的另一种用途
假设有限个候选解有实数分数,平均值为 。至少一个分数不低于 ,也至少一个不高于 。除了从候选集中均匀选一个之外无需其他概率模型。对加权分布,同样的结论适用于正概率的结果,因为期望是分数的凸组合。若平均值等于最大值,每个正概率结果都必须达到最大值;否则较小的分数会降低平均值。
这个定理没有说好结果有多少。例如一个结果分数为 100,另外 99 个分数为零,平均值为 1,却只有一个结果达到或超过平均值。存在性证明也不保证抽样得到好对象有很高概率;要得到高概率算法保证,需要另作集中或抽样分析。
练习
快速检查
(图有四条边,权重为 。随机割的期望重量是多少?)
把权重相加,再取一半。
解答 · 答案
总权重为 8,故期望割重量为 4。只要每条边连接不同顶点,图的具体形状不改变此计算。
快速检查
(部分确定后的图,下一顶点放入 时条件期望为 7,放入 时为 9。当前条件期望是多少?哪种选择使它不下降?)
把两个条件值取平均。
解答 · 答案
当前期望为 。选择条件值为 9 的 。选择 会使这一步的条件期望下降,虽然最终仍可能碰巧得到好割。
快速检查
(三条边均为单位权重的路径,其随机割期望是多少?给出达到最优的割。)
沿路径交替分配两侧。
解答 · 答案
期望为 。沿四个顶点交替分配两侧,可跨越全部三条边,重量为 3。任何割至多使用全部边,所以这是最优值。
快速检查
(某顶点已确定邻点的关联权重在 侧为 2、5,在 侧为 4、1。选择哪侧可使条件期望不下降?)
比较已确定邻点在两侧各自的总权重。
解答 · 答案
两侧总重分别为 7 和 5。将顶点放入 会跨越通往 的 7。赋值之前这些边的期望贡献为 ,之后为 7。连接未确定邻点的边仍各贡献其权重的一半。
快速检查
(条件期望证明是否要求下一顶点的两个选择产生不同的值?)
若两个值相等,全期望公式说明什么?
解答 · 答案
不要求。若 ,两者都等于平均值 ,选择任何一侧都保持不变量。可以用固定规则处理平局,例如总选 。孤立顶点是简单例子:它放在哪侧都不改变边的贡献,两个条件值相同。确定平局规则才能完整说明确定性算法,虽然不同规则可能产生不同的割。