二阶矩方法 | Codeboy's Blog

形式陈述

二阶矩方法利用 $\mathbb E[X]$ 与 $\mathbb E[X^2]$ 控制非负随机变量取正值的概率。对 $X$ 与事件指示函数应用Cauchy–Schwarz 不等式给出

\mathbb P(X>0)\ge\frac{(\mathbb E X)^2}{\mathbb E[X^2]}

只要 $0<\mathbb E[X^2]<\infty$ 。更一般的 Paley–Zygmund 不等式称，对 $0\le\theta<1$ ，

\mathbb P(X\ge\theta\mathbb E X) \ge(1-\theta)^2\frac{(\mathbb E X)^2}{\mathbb E[X^2]}.

对一列非负随机变量 $(X_n)$ ，若 $\mathbb E X_n>0$ 且 $\operatorname{Var}(X_n)=o((\mathbb E X_n)^2)$ ，则 $X_n/\mathbb E X_n\to1$ 依概率。

直觉

期望为正并不保证随机变量常常为正，因为极小概率的巨大值也能撑起均值。二阶矩测量这种质量是否过度集中；若 $\mathbb E[X^2]$ 与 $(\mathbb E X)^2$ 同阶， $X$ 不可能只在极罕见事件上非零。对计数变量，展开 $X^2$ 会显露对象对之间的相关性。

例子与边界

令 $X$ 计数Erdős–Rényi 随机图中的某类子图，展开 $X^2$ 会按两份子图的重叠类型求和，相关性正由这些重叠项体现。若 $X$ 是 Bernoulli 变量，上述二阶矩下界达到等号。二阶矩下界可能很弱，尤其当分布重尾时。仅知方差有限不自动证明 $X>0$ 高概率；必须比较方差与均值平方。方法通常给存在性或集中性，而不直接给构造算法。

若 $X=\sum_i I_i$ 计数某类结构，则

\mathbb E X^2=\sum_i\mathbb E I_i+2\sum_{i<j}\mathbb E[I_iI_j].

独立或弱相关时，交叉项接近乘积，Paley–Zygmund 可给 $P(X>0)$ 的正下界。反例是 $X=n$ 以概率 $1/n$ 出现，否则为零： $\mathbb E X=1$ ，但 $P(X>0)=1/n\to0$ ，而其二阶矩为 $n$ ，准确暴露了尖峰。

推论与应用

概率方法在一阶均值不足时引入方差或二阶矩；与一阶矩方法相比，它能证明对象实际出现而非只控制坏对象平均数。随机图中的子图存在、随机满足性、分枝过程存活概率、随机变量非退化和阈值下界常由此得到；若高阶依赖仍太强，则可能需要 Janson 不等式、鞅或局部引理。

参考资料

Noga Alon and Joel H. Spencer, The Probabilistic Method, 4th ed., Wiley, 2016，Chs. 3–4, second moment and correlation arguments。
Béla Bollobás, Modern Graph Theory, Springer, 1998，Ch. I, first and second moment methods in random graphs。

形式陈述 ​

反向链接

形式陈述