概率方法

概率方法不必给出对象长什么样，只需设计一个随机生成过程，使满足目标性质的概率为正。随机性是证明空间中的加权计数工具：一旦正概率成立，至少存在一个确定性结果。关键工作往往不是“随机选”，而是选择恰当分布和随机变量，让坏事件可以估计。

任意图随机把每个顶点独立放入 $A$ 或 $B$，每条边跨越两侧的概率为 $1/2$，所以期望割边数为 $|E|/2$；因此存在一个割至少包含一半边。这个论证没有给出唯一割，也不说明随机一次高概率达到期望。利用条件期望逐点固定选择，可把这类存在性证明去随机化。

Erdős–Rényi 随机图公理库Erdős–Rényi 随机图Erdős–Rényi random graph · G(n,p) · G(n,m)在固定标号顶点集上独立采样边或均匀采样固定边数的随机图模型。把候选边作为基本随机选择，可用于证明同时具有高色数和大围长的图存在。任何这类论证都必须先给出合法概率空间；“成功概率趋于一”比存在性所需的正概率更强，却仍不自动给出高效确定性构造。对非负随机变量，扩展期望即使为 $+\mathrm{\infty }$，只要 $\mathbb{E}X>0$ 仍可推出某次取值为正；关键是非负性排除了正负抵消。

概率空间公理库Kolmogorov 概率公理Kolmogorov axioms · Probability axioms把概率定义为样本空间上总质量为一的可数可加测度。为有限对象赋分布，一阶矩公理库一阶矩方法First moment method用坏事件计数的期望小于一或 Markov 型界证明好对象存在。、二阶矩公理库二阶矩方法Second moment method用方差或二阶矩控制随机变量偏离均值的概率。和局部引理公理库Lovász 局部引理Lovász local lemma当坏事件概率小且依赖稀疏时，所有坏事件同时不发生的概率为正。分别利用平均、方差与局部依赖证明存在性。随机图、编码、组合设计和算法舍入都由此产生；证明中必须区分“正概率存在”“高概率典型”与“可高效构造”三种不同结论。

在学习下界和流算法中，同一原则也可用随机实例寻找确定坏例子，或把随机性变成可执行的搜索与摘要过程；但从平均表现推出高概率结论，仍需额外的矩或尾界，运行时间与失败概率也必须单独核算。学习的 No-Free-Lunch 原理公理库学习的 No-Free-Lunch 原理No-Free-Lunch theorem for learning若允许任意未见点标注，有限样本不能对所有分布与目标可靠预测。、随机舍入公理库随机舍入randomized rounding把分数解解释为选择概率，以期望、浓缩和修补把凸松弛转成离散近似解。与线性 Sketch公理库线性 SketchLinear sketch以线性映射 Sf 压缩频率向量，使更新与分布式摘要可直接相加。分别展示了这三种用法。