二阶矩方法

二阶矩方法（second moment method）利用随机变量的均值和平方的均值，估计某种对象出现的概率。它常用于组合数学：把所求对象的个数记为非负随机变量 $X$，先计算 $𝔼X$，再通过 $𝔼X^2$ 控制“平均值主要由极少数巨大取值贡献”的可能性。

例如，在五个顶点之间独立地以概率二分之一放置每条边，平均有 $5/16$ 个孤立顶点。但这个均值不是“出现孤立顶点的概率”。一张图可以有多个孤立顶点；需要另算对象之间的共同出现，才能从计数均值得到概率下界。

非负随机变量的出现概率

设 $X\ge 0$，且 $0<𝔼X^2<\mathrm{\infty }$。则 $$\mathbb{P}(X>0)\ge \frac{(𝔼X{)}^2}{𝔼X^2}.$$ 证明。 用 ${\mathrm{𝟏}}_{\{X>0\}}$ 表示事件的指示变量。由于零值部分不贡献期望， $$𝔼X=𝔼[X{\mathrm{𝟏}}_{\{X>0\}}].$$ 对右侧应用柯西不等式，得到 $$(𝔼X{)}^2\le 𝔼X^2\cdot 𝔼{\mathrm{𝟏}}_{\{X>0\}}^2=𝔼X^2\cdot \mathbb{P}(X>0).$$ 分母严格为正，除过去即得结论。这里没有要求 $X$ 为整数，也没有要求组成它的计数指标相互独立。

令 $\mu =𝔼X>0$、${\sigma }^2=\mathrm{Var}X$。由于 $𝔼X^2={\mu }^2+{\sigma }^2$，上式也可写成 $$\mathbb{P}(X>0)\ge \frac{1}{1+{\sigma }^2/{\mu }^2}.$$ 若一列随机变量满足 ${\sigma }_n^2/{\mu }_n^2\to 0$，那么对象出现的概率趋于一。这是一个随规模变化的结论，不能只凭某个有限样本的均值很大就宣称“几乎必然”。

均值本身不足以做到这点。取 $X=M^2$ 的概率为 $1/M$，其余时间为零，则 $𝔼X=M$ 随 $M$ 增大，但 $\mathbb{P}(X>0)=1/M$ 反而趋于零。此时二阶矩为 $M^3$，上面的下界恰好为 $1/M$。

计数指标与共同出现

若 $X=\sum _{i=1}^n{I}_i$，其中 $I_i\in \{0,1\}$，展开平方时对角项满足 $I_i^2=I_i$，故 $$𝔼X^2=\sum _i𝔼I_i+2\sum _{i<j}𝔼(I_i{I}_j).$$ 其中 $𝔼(I_i{I}_j)$ 是两个事件同时发生的概率。只有确认两事件独立，才可写成两概率的乘积。等价地， $$\mathrm{Var}X=\sum _i\mathrm{Var}{I}_i+2\sum _{i<j}\mathrm{Cov}(I_i,I_j).$$ 许多二阶矩问题的关键正是识别哪些对象重叠，以及这种重叠使共同出现的概率怎样改变。

随机图中的孤立顶点

考虑随机图 G(n,p)：固定 $n\ge 2$ 个有标号顶点，各条可能的无向边独立以概率 $p\in [0,1)$ 出现。记 $q=1-p$，$I_i$ 表示顶点 $i$ 孤立。它的 $n-1$ 条邻边必须全部缺失，所以 $$𝔼I_i=q^{n-1},𝔼X=n{q}^{n-1}.$$ 顶点 $i,j$ 同时孤立时，两组缺边中，共用的边 $ij$ 只能计一次。需要缺失的不同边共有 $$2(n-1)-1=2n-3$$ 条。因此 $$𝔼(I_i{I}_j)=q^{2n-3},𝔼X^2=n{q}^{n-1}+n(n-1)q^{2n-3}.$$ 孤立事件并不独立：乘积 $q^{2n-2}$ 少考虑了共用边的作用。代入二阶矩下界，得到 $$\mathbb{P}(X>0)\ge \frac{n{q}^{n-1}}{1+(n-1)q^{n-2}}.$$

两个顶点同时孤立时，图中七条虚线边都要缺失。公共边 ab 不能在指数中重复计算。

对 $n=5,p=1/2$，各项都是可精确计算的分数： $$\mu =\frac{5}{16},𝔼X^2=\frac{5}{16}+20\frac{1}{128}=\frac{15}{32},\mathbb{P}(X>0)\ge \frac{5}{24}\approx \mathrm{0.20833.}$$ 这里方差为 $15/32-25/256=95/256$。枚举十条可能边的 $2^{10}=1024$ 种等概率图，可以核对：没有孤立顶点的图有 $768$ 个，恰有一个的有 $205$ 个，两个的有 $40$ 个，三个的有 $10$ 个，五个的有一个。因此真实出现概率是 $256/1024=1/4$，确实大于下界；这些计数也还原了上述一阶矩和二阶矩。

实线由全部1024种有标号图按边数加权求得，虚线是二阶矩下界。两者在 p=1 时均为零；该端点 X 恒零，须单独处理而不对零二阶矩作除法。

方差界与有解变式

在 $\mu >0$ 时，事件 $X=0$ 蕴含 $|X-\mu |\ge \mu$，所以 Chebyshev 不等式另给出 $$\mathbb{P}(X=0)\le \frac{\mathrm{Var}X}{{\mu }^2}.$$ 这个界适合证明相对方差很小时出现概率趋于一，但有限算例中右端可能大于一；不能把这样的数当作精确概率。前述非负变量下界始终落在 $[0,1]$。

变式。 四次独立试验的成功概率都为 $1/4$，$X$ 为成功次数。这里不同成功指标独立，因此 $$𝔼X=1,𝔼X^2=4\frac{1}{4}+12\frac{1}{16}=\frac{7}{4}.$$ 至少成功一次的概率不小于 $4/7$。直接从全失败事件计算，真实值是 $1-(3/4{)}^4=175/256$，约 $0.68359$。先推概率界、再与可算真值比较，可以辨认这个方法提供的是保证而非精确值。

适用边界

二阶矩有限是上面分母和柯西论证的条件；若二阶矩无穷，该下界不能直接使用。对于带正负号的 $X$，事件 $X>0$ 也不再满足本篇的非负论证。做随机计数时，选取什么作为 $X$ 很重要：高度重叠的对象可能使协方差很大，得到的界虽正确却很弱。可以改计更少重叠的对象，或利用更强的概率工具，但不能把未验证的独立性当成简化计算的理由。

相关条目

• 概率方法：由随机构造推出确定性的存在结论。
• 埃尔德什雷尼模型：本篇孤立顶点算例的随机机制。