概率方法是一类通过在数学对象的构造或选取过程中引入随机性,来证明其存在性的技巧。这类证明不直接给出满足所需性质的具体对象,而是定义一组可能的对象,为它们赋予概率,并证明得到满足要求的对象的概率为正。由此得出的结论是确定的:至少存在一个这样的对象。
这一方法在组合数学、图论和理论计算机科学中尤为重要。在这些领域,直接构造对象可能很困难,但对一批对象进行整体研究却相对容易。概率方法涵盖的技巧十分广泛,从初等的计数与平均值论证,到集中不等式、依赖关系论证以及随机过程分析,不一而足。有些证明仅能确立存在性,无法给出高效的构造方法;另一些证明则能直接导出随机算法,或可转化为确定性算法。
基础与历史发展
概率存在性证明首先构造一个 概率空间 ,其中的样本点代表候选对象。若 是样本点满足所有所需性质的事件,则
意味着 非空。虽然这一推论很简单,但选择一个有用的概率空间并证明上述不等式,可能需要相当巧妙的构思。随机选择是证明的一部分,却不一定是最终断言存在的对象本身的一部分。
概率空间不必描述自然发生的随机现象。我们可以将图、着色、集合系统或数值赋值随机化,目的仅仅是揭示有用的平均值或依赖关系。均匀抽样很常见,但非均匀的随机选择往往更有效。例如,以概率 独立地选取图中的每个顶点,就引入了一个可供优化的参数,用来平衡所选顶点的数量与不希望出现的边的数量。
概率为正与概率趋于一之间有一个重要区别。对于以大小 为指标的一列随机对象,若某个性质成立的概率在 时趋于一,就称该性质以高概率成立。对于每个相关的大小,正概率就足以证明存在性;而高概率结果还能提供有关典型对象的更多信息。即使正概率极其微小,也能确立存在性,不过这可能使反复随机抽样在计算上变得不可行。
保罗·埃尔德什使概率推理成为二十世纪离散数学的核心工具。他于1947年给出的对角拉姆齐数下界成为一个标志性范例:通过对完全图的边进行随机着色,可以证明存在避免出现大型单色完全子图的着色。1959年,他利用随机图证明,图的围长和色数可以同时任意大。这些例子表明,看似相互冲突的结构要求可以同时得到满足。
埃尔德什与阿尔弗雷德·雷尼从1959年和1960年发表的论文开始,系统地发展了随机图理论,大大拓宽了此类论证的应用范围。后续进展包括埃尔德什与拉斯洛·洛瓦斯在1975年发表的研究中提出的洛瓦斯局部引理,以及概率存在性论证的构造性版本。诺加·阿隆与乔尔·斯潘塞合著的《概率方法》于1992年首次出版,帮助围绕一套明确的技巧体系梳理了这一领域。
这种方法并不限于有限集合。在由无穷序列、函数或几何构型组成的空间上,概率测度同样可以用来证明存在性。在这些情形中,可测性与极限论证十分重要,而某个性质以概率一成立,并不意味着每一个可能的对象都具有该性质。
一阶矩、联合界与拉姆齐理论
最简单的概率存在性论证是对不希望出现的特征进行计数。设 是一个非负整数值随机变量,记录随机构造中缺陷的个数。只要出现缺陷,就有 ,因此
所以, 意味着 。这称为一阶矩方法,因为它只需要用到 的期望值。
一种等价的表述使用联合界。若 是不希望发生的事件,则
如果右侧之和小于一,就存在某个结果,使所有这些事件都不发生。这里不需要任何独立性假设。当这些事件大量重叠时,这个界可能很粗糙,但其普适性使它成为一个基本的出发点。
一个经典应用来自拉姆齐理论。对角拉姆齐数 是满足以下条件的最小整数 :无论怎样将完全图 的边染成红、蓝两色,其中都包含一个单色的 。为得到下界,将每条边相互独立地染成红色或蓝色,两种颜色的概率各为 。对于一个固定的、含 个顶点的集合,其全部 条边颜色相同的概率为
因此,单色 的个数的期望值为
只要这个量小于一,就存在不含单色 的染色,从而有 。
这一估计已经给出了指数级下界。更精确地说,利用 ,对于任意固定的常数
当 充分大时,都可以取 。这里的 是自然常数e。因此,这一论证确立了一个量级为 的下界,却没有给出达到该下界的具体染色。
同样的推理也适用于许多规避问题。如果一族禁用构型至多有 个成员,而每个成员出现的概率至多为 ,那么 就能保证存在一个不含任何禁用构型的构造。主要工作往往在于准确计算禁用构型的数量,或选择一种分布,使它们出现的概率足够小。
一阶矩小于一是充分条件,而不是必要条件。即使期望值大于一,也仍然可能存在没有缺陷的结果;只是这一估计无法证明其存在。反过来,如果所需构型的期望个数趋于零,那么哪怕只出现一个此类构型的概率也趋于零。后一种用法使一阶矩成为证明随机模型中某类构型不存在的有效工具。
期望的线性性与平均值论证
另一个基本原理是,至少有一种结果不差于平均水平。对于有限概率空间上的实值随机变量 ,存在一种结果使得 ,也存在一种结果使得 。即使不显式计算任何事件的概率,也能据此将平均值转化为存在性定理。
主要的计算工具是期望的线性性:
与概率的乘法法则不同,这一恒等式不要求统计独立性。因此,即使所计数的各项特征之间存在很强的相互影响,也可以为每项特征引入一个示性函数,从而将复杂的计数分解开来。
考虑一个有 条边的无向图。将每个顶点独立地以相等概率分到两类中的一类。一条边跨越这两类的概率为 。若用 表示跨越两类的边数,则
因此,必定存在一种划分,使至少一半的边跨越两类。这为最大割问题提供了一个存在性保证,而无须考察图的整体结构。计算这一期望时,并不要求各条边是否跨越两类的示性变量相互独立。
一个更精细的例子给出了独立集大小的下界;独立集是指内部没有边相连的顶点集合。从所有顶点排列中均匀随机地选取一个排列,并保留所有排在其全部邻点之前的顶点。两个相邻顶点不可能同时被保留,否则它们各自都必须排在对方之前。因此,保留下来的顶点构成一个独立集。
若顶点 的度为 ,那么它在自身及其所有邻点中排在最前面的概率为 。因此,独立数满足 Caro–Wei 界:
由柯西—施瓦茨不等式可进一步得出,一个有 个顶点、 条边的图满足
这个例子说明,相比于均匀随机地选取一个子集,随机排列能够更有效地利用局部结构信息。
平均值论证也揭示了保证值与典型值之间的区别。知道 ,可以证明至少有一种结果达到 ,却不能说明大多数结果都能达到这一水平。很大的期望可能只是由少数极端结果造成的。要得到稳健的抽样算法,或同时对多个量作出保证,通常还需要进一步控制波动。
因此,线性性的威力不在于它能解决所有依赖性问题,而在于当我们只关心平均值时,它能绕开依赖性。随机划分、随机排列、随机符号和随机子集,常常能将确定性的优化问题转化为简单的局部概率之和。
修正法与缺陷的消除
修正法先生成一个可能不满足要求的随机对象,再对其进行修补。论证并不要求把每种缺陷出现的概率都压低到足以保证所有缺陷均不出现,而是允许存在缺陷,只要消除缺陷的代价小于随机构造最初带来的收益即可。这里所考察的随机变量,往往是对象的大小与修补所需代价之差。
例如,设一个图有 个顶点和 条边,以概率 独立地选取每个顶点。用 表示选中的顶点集合,用 表示两个端点都被选中的边的集合。对 中的每条边至多删除一个顶点,就能留下一个大小至少为
的独立集。由于
至少有一种结果能得到大小不小于 的独立集。当 时,取 ,便得到下界 。尽管这个界弱于前文中考虑了顶点度数的界,但这一论证展示了灵活的“先选取,再删除”策略。
埃尔德什关于大围长与大色数的定理是一个更深入的应用。图的围长是其最短圈的长度,而色数是对顶点着色、使相邻顶点颜色不同所需的最少颜色数。对于任意两个给定的正整数 和 ,都存在一个图,其围长大于 ,色数大于 。
为了说明其中的机制,固定 ,取一个有 个顶点的随机图,其中每条边独立地以概率
出现。长度为 的圈的期望个数至多为
对 求和可知,短圈的期望个数至多为 的常数倍,其中常数依赖于 。
同时,令
大小为 的独立集的期望个数满足上界
且该上界趋于零。负指数项起主导作用,因为 按 的某个正幂增长,速度快于 。
因此,当 足够大时,存在一个图,其短圈少于 个,且没有大小为 的独立集。从每个短圈中删除一个顶点。剩下的图至少有 个顶点,围长大于 ,独立数小于 。每个颜色类都是独立集,因此该图的色数至少为 ,而这个值趋于无穷大。
这里的关键在于,删除顶点能够破坏短圈,却不会产生更大的独立集。当所需的全局性质在修补操作后仍能保留,且每个局部缺陷的修补代价都有界时,修正法最为有效。
二阶矩与稀有构型的存在性
仅靠一阶矩通常无法证明所需构型会出现。计数的期望值很大,可能只是因为某些罕见结果包含了数量极多的构型副本。二阶矩方法通过考察 ,或等价地考察方差,来控制这种可能性:
对于任何二阶矩有限的非负随机变量,柯西–施瓦茨不等式给出
事实上,由于 ,对这两个因子应用该不等式即可得到结论。如果
那么上述下界趋于一。因此,足够小的相对方差不仅能证明所需构型存在,还能证明它以高概率出现。
核心任务通常是计算构型之间的重叠。若
表示候选构型的数量,则
这里,协方差衡量两个候选构型是否倾向于同时出现。在由相互独立的基本随机选择生成的随机结构中,若两个候选构型所涉及的选择集合互不相交,它们就是独立的,对协方差的贡献为零。因此,只有相互重叠的候选构型需要详细分析。
例如,设 表示随机图 中三角形的数量,其中每条可能的边都以概率 独立出现。那么
没有公共边的不同三角形彼此独立,即使它们有一个公共顶点也是如此。共用一条边的两个三角形共涉及五条不同的边,因此它们同时出现的概率为 。对这样的三角形对进行计数,可得
除以期望的平方后,这两部分贡献的阶为
若 ,两项都趋于零,因此图中以高概率存在三角形。若 ,三角形数量的期望趋于零,因此一阶矩方法表明,图中以高概率不存在三角形。结合这两个论证,就确定了三角形出现的阈值尺度为 。
当构型之间存在多种重叠方式,或构型往往成簇出现且彼此高度相关时,二阶矩方法就更难应用。方差很大本身并不能证明所需对象不太可能出现;它只意味着这一估计不足以解决问题。更精细的计数、条件化,或改用另一个随机变量,都可能重新得到有用的界。选择对什么进行计数,可能与选择何种随机模型同样重要。
集中不等式与同时控制
许多存在性论证要求多个量同时保持在各自均值附近。切比雪夫不等式给出
但当约束很多时,这种多项式衰减可能不够强。当随机变量具有适当的独立性,或其对输入变化的敏感程度有限时,集中不等式可以给出更强的界。
设 是一组独立伯努利随机变量之和,均值为 ,则一个标准的切尔诺夫界为
由于概率呈指数衰减,可以将这一估计与针对大量事件的并集界结合使用。证明利用指数矩:对于 ,
随后利用独立性,将期望分解为易于处理的各项之积。通过优化参数 ,便可得到尾部概率估计。
例如,在 中,每个顶点的度都服从均值为 的二项分布。对每个顶点应用切尔诺夫界,再使用并集界,可得
对于固定的 ,当 超过 的某个足够大的常数倍时,右侧趋于零。各顶点的度并不相互独立,但并集界并不要求这一点。
对于并非简单求和形式的函数,也可能有集中性。设 相互独立,且改变第 个坐标,使 的变化不超过 。有界差分不等式给出
对于由许多微小贡献共同决定的量,即使其内部表达式产生了复杂的依赖关系,这一不等式仍然有用。
一种相关方法是依次揭示各次随机选择,并跟踪最终所考察量的条件期望。由此得到的序列是一个鞅,而有界增量使我们能够应用阿祖马–霍夫丁型估计。这将集中性与自适应构造及随机过程联系起来;在这些情形中,一步之后的状态会影响下一步。
必须仔细核查敏感度界。仅改变一条边,就可能使三角形数量改变多达 ,因此,直接套用有界差分不等式得到的估计,可能远弱于利用三角形计数实际结构的论证。当集中性工具的假设反映的是典型影响的尺度,而不只是理论上可能出现的最大变化时,这些工具最能发挥作用。
洛瓦兹局部引理与稀疏依赖
联合界将所有坏事件视为一个整体来处理。当事件数量很多时,即使每个事件只依赖于少数其他事件,联合界也可能失效。洛瓦兹局部引理利用这种有限的依赖关系,证明所有坏事件可以同时被避开。
设 为坏事件。依赖图以这些事件为顶点,并具有如下性质:每个 都与其非邻点所对应的事件族独立。更准确地说, 与这些事件生成的 σ-代数独立。这一条件比两两独立更强,也是标准表述中不可或缺的条件。
对称形式的局部引理指出,如果对每个 都有
成立,依赖图中每个事件至多有 个邻点,并且
那么
关键参数是局部依赖度 ,而不是事件总数 。约束的数量可以极其庞大,只要相对于与每个约束相互关联的其他约束的数量而言,该约束被违反的概率足够小即可。
一个应用是对 -一致超图进行二染色;这种超图的每条边都是恰好包含 个顶点的集合。将各顶点独立地染成红色或蓝色,并令 表示边 为单色的事件。于是
不相交的边所对应的事件依赖于互不重叠的顶点集合的颜色。如果每个顶点至多属于 条边,那么任意一条边至多与 条其他边相交。因此,只要
就存在正常二染色。与初等的联合界判据不同,这一条件与边的总数无关。
非对称形式允许各事件具有不同的概率和依赖邻域。如果存在数 满足
其中 是 的邻域,那么避开所有坏事件的概率为正。参数 量化了为各个约束分配的余量,对于不规则结构,它们可以显著改进所得的界。
局部引理还可用于布尔公式的可满足性、调度、横截集和图染色等问题。例如,在一个合取范式公式中,某个子句不被满足这一坏事件,只依赖于该子句中出现的变量。在乘积分布下,没有共享变量的子句彼此独立。因此,即使子句数量多到无法用联合界论证可满足性,只要每个变量的出现次数受到适当限制,仍可能保证公式可满足。
随机结构、阈值与更广泛的应用
概率方法与随机图研究紧密相关,但侧重点有所不同。概率存在性证明只需要有一个成功的结果。随机图理论则关心某种性质出现的概率有多大、这一概率如何随参数变化,以及典型对象是什么样的。关于典型行为的结果,往往可以直接导出很强的存在性定理。
两种基本模型是 和 :前者中每条边以概率 独立出现,后者则从所有具有 个带标号顶点且恰有 条边的图中均匀选取。前者提供了独立性,后者则固定了边的总数。在两者之间转换有时很有用,但不能不加论证就将这两个模型互换,因为以边数为条件会引入依赖关系。
阈值描述的是某种性质从不太可能出现转变为很可能出现时的参数尺度。连通性有一个尤为精确的转变规律。对固定的实数 ,若
则
在这一尺度上,孤立顶点的数量依分布收敛于均值为 的泊松分布;从渐近意义上说,孤立顶点构成了连通性的主要障碍。这一结果将局部计数与对较大非连通分支的控制结合起来。
其他概率构造可以产生具有很强的全局连通性质的稀疏图。在扩展图中,较小的顶点集具有相对较大的邻域或边界。扩展性的价值在于,它使较少的边数与图中快速的信息传递得以兼顾。随机正则图是其中的重要例子,而显式构造则将这一领域与代数和谱方法联系起来。
在信息论中,随机编码证明了某些消息集合的存在性,其中各条消息之间的差异足够大,因而能够容忍传输错误。对于长度为 的二进制分组码,汉明距离计算的是两个字在多少个位置上不同。若两个码字的距离至少为 ,则至多 个位置上的错误不会使它们的译码邻域重叠。随机选取、汉明球体积估计以及删除相互冲突的码字,可以给出纠错码的存在性界。
概率论证也应用于离散几何。随机抽样可以选出较小的子集,使其与集合系统中每个足够大的范围都有交集。这类抽样定理是几何近似和范围搜索技术的基础。它们能否奏效,不仅取决于范围的数量,还取决于某些结构性的复杂度度量;这些度量限制了一个范围族能在有限样本上诱导出多少种不同的交集。
在这些应用中,随机模型必须体现确定性问题的实际约束。独立抽取边对不受限制的图很方便,但它并不能自动产生正则图、保持几何可实现性,或确保精确的代数恒等式成立。当这些约束不可或缺时,就需要采用条件化、有结构的随机选择或修补程序。
构造性证明、随机算法与去随机化
证明某个结果以正概率出现,并不自动意味着能给出高效的算法。若一次成功的概率为 ,且能够判断是否成功,那么独立重复采样平均需要 次尝试。一个证明可能只说明 ,却没有给出有用的下界;也可能验证所需性质本身就在计算上十分困难。
条件期望法可以将某些基于平均值的证明转化为确定性构造。假设目标量 取决于一系列选择。在任意部分赋值下,当前的条件期望都是作出下一步各种可能选择后的条件期望的加权平均。因此,至少有一种选择能够使其保持不变或有所提高。每一步都固定这样的选择,最终便能得到一个完整对象,其目标值至少等于最初的期望。
对于割问题,可以逐个确定每个顶点属于哪一侧。每一步都将下一个顶点分配到这样的一侧:在其余顶点仍随机分配的情况下,跨越两侧的边数的期望不会下降。当所有顶点都分配完毕后,便不再有随机性,而最终的割至少包含 条边。由于相关的条件期望可以直接根据边来计算,这一过程是高效的。
对于需要避免缺陷的问题,可以跟踪缺陷数量的条件期望。如果初始期望小于一,并且每次选择都保持这一上界,那么最终的缺陷数量就是一个小于一的非负整数,因此必为零。更一般的悲观估计量则用一个便于计算、且在逐步作出选择时具有适当性质的上界,来替代难以处理的条件概率或条件期望。
局部引理也有一个强有力的构造性版本。2010 年,罗宾·莫泽和加博尔·塔尔多什证明了变量框架下的算法版本:各个坏事件由相互独立的随机变量决定,一个事件的邻域由与它共享变量的事件组成。他们的重采样算法从随机赋值开始,反复找出一个已发生的坏事件,并且只对该事件所依赖的变量重新采样。
在满足参数为 的非对称局部引理条件时,事件 的期望重采样次数至多为
因此,如果能够高效地检测坏事件并进行重采样,而且这些上界的总和处于可控范围内,存在性证明就能给出一种高效的随机构造。分析时必须考虑先前重采样步骤所造成的依赖关系;仅凭原始变量的独立性,并不足以将接连进行的修复视为相互独立。
去随机化也会使用有限独立性分布和伪随机生成器。如果一个证明只需要少量矩恒等式,就未必需要完全的随机性,从而可以在小得多的样本空间中进行搜索。随机舍入提供了另一条通向计算的途径:将线性规划的分数解用概率来解释,再通过集中性估计或修正法控制所得的整数解。
这些构造性进展将几个不同的问题区分开来:对象是否存在,随机采样能否快速找到它,能否高效验证结果是否成功,以及是否存在确定性构造。概率证明可能解决其中某一个问题,却并不解决其余问题。