一阶矩方法

一阶矩方法最重要的选择不是套哪条不等式，而是数什么。与其直接计算“所有要求同时满足”的概率，不如给每项违规记一个指标，把它们加成总违规数。分别计算每项违规概率往往很容易，彼此复杂的关联也不会妨碍求和。

整数性把“小于一”变成“可以为零”：如果每个结果都至少违反一项要求，平均违规数就不可能小于一。对于最大化问题则反过来数收益；只要平均收益是 $L$，至少有一个对象取得 $L$ 或更多。这两种用法分别解决“排除全部坏结构”和“达到某个收益水平”。

超图二染色：边之间可以重叠 ​

给有限超图的每个顶点独立、等概率地染成红色或蓝色，所有边都非空。若边 $e$ 含 $k_e$ 个顶点，它全红的概率为 $2^{-k_e}$，全蓝也一样；两个事件互斥，所以

令 $X$ 为单色边数，得到

只要该和小于 $1$，就存在没有任何单色边的二染色。特别地，若每条边恰有 $k$ 个顶点、总边数为 $m$，则 $m<2^{k-1}$ 是一个充分条件。例如 $4$-一致超图只有 $7$ 条边时，坏边期望为 $7/8<1$，无论边如何重叠都可二染色。[2]

非空边条件不可省：对空边，“全部红色”和“全部蓝色”同时真，不能当作两个不交事件相加。

这里顶点的随机颜色独立，用于算单条边的概率；不同边若共享顶点，单色事件通常相关，却不妨碍最后的期望相加。把这两处“独立性”的作用分开，才能看清方法究竟需要什么。

最大割：从平均收益抽出好对象 ​

对一个有 $m$ 条边的有限简单无向图，把每个顶点独立等概率地放入两侧。对任意边，两个端点恰好分居两侧的概率是 $1/2$。所以跨边数 $Y$ 满足

于是存在至少有 $m/2$ 条跨边的割；利用整数性，可写成至少 $\lceil m/2\rceil$ 条。图中边事件的依赖关系不影响这一证明。对 $n\ge 1$ 个元素的均匀随机排列，固定点数也是相同的分解：每个位置固定的概率为 $1/n$，总期望为 $1$；但这个等式单独还不能推出存在零固定点的排列。

哪些结论不能由均值读出 ​

严格不等号不能随意放松。$X\equiv 1$ 的期望等于 $1$，却从不为零；整数性也不能删掉，因为 $X\equiv 1/2$ 满足 $\mathbb{E}X<1$，仍然从不为零。若 $X$ 带权，而每个正值至少为 $a>0$，应改用 $\text{Pr}(X>0)\le \mathbb{E}X/a$。

均值很大也未必经常出现正值。令 $X=M^2$ 的概率为 $1/M$，其余时候为 $0$，则 $\mathbb{E}X=M$，但 $\text{Pr}(X>0)=1/M$ 反而趋于零。要排除这种“均值由罕见大值撑起”的情形，需要二阶矩方法理路二阶矩方法Second moment method从非负变量的二阶矩证明正概率与相对集中，并逐类计算随机图三角形的精确方差、有限分布和密度极限。等额外信息。

因此，$\mathbb{E}X<1$ 是零坏结构存在的充分条件，不是必要条件；算出 $\mathbb{E}X\ge 1$ 只表示这条充分条件未满足。另一方面，若已经能证 $\mathbb{E}X\to 0$，则 Markov 界确实给出 $\text{Pr}(X=0)\to 1$，此时不仅有存在性，还有高概率保证。

从存在性到逐步构造 ​

最大割的论证还可以通过条件期望理路条件期望Conditional expectation以信息分组的加权平均建立条件期望直觉，再连接测度定义、最小均方预测、塔式性质和可计算反例。去随机化。固定一部分顶点的侧别后，考察把下一个顶点放左、放右这两种选择；它们对应的条件期望的平均值，正是当前条件期望。因此至少一个选择不会降低它。

每次选不降低期望的一侧，直到所有顶点都确定。最后没有随机性，条件期望就是实际割边数，于是所得割仍至少有 $m/2$ 条边。能实施这个过程的原因，是两种选择下的条件期望可以高效计算；一般存在性证明并不自动具备这个计算条件。

在这个具体问题中，计算也很简单：尚未决定的邻居各贡献 $1/2$；已经决定的邻居中，把当前顶点放到数量更多者的对侧，就能最大化即时跨边贡献。每条边只需按邻接结构处理常数次。这是条件期望理路条件期望Conditional expectation以信息分组的加权平均建立条件期望直觉，再连接测度定义、最小均方预测、塔式性质和可计算反例。去随机化，而不是枚举所有 $2^n$ 个割。

有限假设类中的坏规则计数 ​

设非空有限假设类 $\mathcal{H}$ 固定，$0<\epsilon ,\delta <1$，样本为来自同一分布的 $n$ 个独立标注样本。若某规则的真实分类错误率大于 $\epsilon$，它在全部样本上碰巧零错误的概率至多为 $(1-\epsilon {)}^n\le e^{-n\epsilon }$。令 $X$ 数“真实错误率大于 $\epsilon$、却在样本上零错误”的规则，就有

取 $n\ge (\ln |\mathcal{H}|+\ln \left(1/\delta \right))/\epsilon$，坏规则幸存的概率至多为 $\delta$。这个界排除了坏的零训练误差规则；它本身不保证存在任何零训练误差规则，后者还需可实现性等条件。

这些论证都属于概率方法理路概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。：随机性服务于确定性结论。反向的No-Free-Lunch理路学习的 No-Free-Lunch 原理No-Free-Lunch theorem for learning若允许任意未见点标注，有限样本不能对所有分布与目标可靠预测。论证也会对目标取平均，再抽出一个使学习器表现较差的固定目标；平均下界与高概率下界是不同承诺，必须按实际需要分别证明。