形式陈述

概率方法通过在有限或可测对象空间上定义随机对象，并证明某个目标事件 $E$$E$ 的概率严格为正，推出至少存在一个确定对象满足该性质：

$$ \Pr(E)>0\Longrightarrow E\ne\varnothing. $$$$\text{Pr}(E)>0⟹E\ne \varnothing .$$

常见策略包括：证明坏事件并的概率小于一；构造非负随机变量 $X$$X$ 并证明 $\mathbb E X>0$$\mathbb{E}X>0$ 从而存在 $X>0$$X>0$；或证明坏对象计数 $Y$$Y$ 满足 $\mathbb E Y<1$$\mathbb{E}Y<1$ 从而存在 $Y=0$$Y=0$。方法本身是存在性论证，随机性位于证明或构造过程，不表示结论对象必须随机。

直觉

与其直接寻找一个极难描述的好对象，不如随机撒网；只要好对象占有正概率，就已证明它至少存在。

例子与边界

随机给图的顶点二染色，可通过期望证明存在割包含至少一半边。随机图可证明同时具有高色数和大围长的图存在。仅有事件概率“非零但可能未定义”不够，必须先有合法概率空间。若证明成功概率趋于一，当然比正概率更强，但存在性只需正概率。概率方法可能不给高效确定性算法；要算法化需条件期望、重采样或去随机化。期望为正推出某次取值为正需随机变量可积且不能由正负抵消来表达目标，通常选非负计数变量。

推论与应用

概率方法构造极值图、编码、集合系统和算法证书，并催生局部引理与去随机化。

参考资料

• Noga Alon and Joel H. Spencer, The Probabilistic Method, 4th ed., Wiley, 2016，Ch. 1, the basic probabilistic method。
• Béla Bollobás, Modern Graph Theory, Springer, 1998，Ch. I, random graphs and probabilistic existence。