形式陈述

一阶矩方法只使用随机变量的期望。若 $X\ge0$$X\ge 0$，Markov 不等式给出

$$ \Pr(X\ge t)\le\frac{\mathbb E X}{t} \qquad(t>0). $$$$\text{Pr}(X\ge t)\le \frac{\mathbb{E}X}{t}(t>0).$$

特别地，若 $X$$X$ 是非负整数值坏结构计数且 $\mathbb E X<1$$\mathbb{E}X<1$，则

$$ \Pr(X\ge1)\le\mathbb E X<1, $$$$\text{Pr}(X\ge 1)\le \mathbb{E}X<1,$$

故 $\Pr(X=0)>0$$\text{Pr}(X=0)>0$，存在完全没有坏结构的对象。另一方面，任意可积实随机变量都存在某个结果使 $X\ge\mathbb E X$$X\ge \mathbb{E}X$，也存在某个结果使 $X\le\mathbb E X$$X\le \mathbb{E}X$；否则期望定义会矛盾。线性期望不要求各指标变量独立。

直觉

期望是所有样本值的加权平均；若坏对象平均不到一个，不可能每个样本都至少有一个坏对象。把总计数拆成指标变量后，即使事件相关，期望仍可逐项相加。

例子与边界

随机排列中固定点数 $X=\sum_i I_i$$X=\sum _i{I}_i$，每个 $\mathbb E I_i=1/n$$\mathbb{E}{I}_i=1/n$，故 $\mathbb E X=1$$\mathbb{E}X=1$，无需固定事件独立。随机二染色图顶点时，单边成为跨边的概率为一半，所以期望割边数为 $m/2$$m/2$，存在至少含 $m/2$$m/2$ 条边的割。条件 $\mathbb E X<1$$\mathbb{E}X<1$ 必须严格；若等于一，可能每个样本恰有一个坏对象。期望小只能给存在性和粗尾界，不能自动给高概率集中；后者通常需二阶矩、Chernoff 界等。若坏结构带权且最小正权不为一，应使用相应阈值。

推论与应用

一阶矩方法是随机组合、近似算法和去随机化中最基础的期望证书。

参考资料

• Noga Alon and Joel H. Spencer, The Probabilistic Method, 4th ed., Wiley, 2016，Ch. 1, first moment and expectation arguments。
• Béla Bollobás, Modern Graph Theory, Springer, 1998，Ch. I, expectation and random graph counts。