二阶矩方法 | Codeboy's Blog

形式陈述

设 $X\ge0$ 且 $0<\mathbb E[X^2]<\infty$ 。二阶矩方法给出

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

更一般的 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]}. \tag{2}

取 $\theta=0$ 时，(2) 左侧是 $\mathbb P(X\ge0)$ ，与 (1) 中的严格正事件不同；(1) 可直接证明，不需在事件边界上作替换。

对一列二阶矩有限、均值 $\mu_n=\mathbb E X_n>0$ 的随机变量，若

\operatorname{Var}(X_n)=o(\mu_n^2),

则

X_n/\mu_n\longrightarrow1

在均方意义下成立，因而也依概率成立。这个相对集中结论本身不需要非负性；当 $X_n$ 非负且计数某类对象时，它还给出对象存在的高概率结论。

本页的完整计数例子是独立边随机图 $G(n,p)$。若 $T$ 按无序三顶点集计数三角形， $n\ge3$ 、 $0\le p\le1$ ，则

\mathbb ET=\binom n3p^3,

\boxed{ \operatorname{Var}T =\binom n3p^3(1-p^3)+12\binom n4p^5(1-p). } \tag{3}

约定 $n=3$ 时 $\binom n4=0$ 。对于固定 $0<p<1$ ，(3) 推出 $T/\mathbb ET\to1$ ；相应三角形密度趋于 $p^3$ 。

直觉

正期望可能完全由很罕见的巨大取值撑起。二阶矩把这些尖峰放大；若它与均值平方相近，质量就不能过度集中在罕见事件上。

计数变量通常是指示变量之和。它的方差不仅包括每个对象的单独波动，还包括对象对之间的协方差。随机图中，两份三角形只有共享边时才共享底层随机开关；共享一个顶点、但没有共享边，并不会在 $G(n,p)$ 中制造依赖。正确区分这些重叠类型，才能得到方差里的两个不同数量级。

例子与边界

四顶点均匀随机图的全部三角形取值

取 $n=4,p=1/2$ 。六条候选边独立，所以每个标号图的概率都是 $1/64$ 。三角形数 $T$ 的分布为：

$T$	标号图数量	概率
$0$	$41$	$41/64$
$1$	$16$	$16/64$
$2$	$6$	$6/64$
$3$	$0$	$0$
$4$	$1$	$1/64$

恰有一个三角形时，先选三角形的三个顶点，有四种选择；第四个顶点可以没有邻点或恰有一个邻点，共四种情形，得到 $16$ 个图。若第四个顶点连到三角形中两个顶点，就得到恰有五条边的图，它们由缺少的边确定，共六个，各含两个三角形。连到全部三个顶点则是 $K_4$ ，有四个三角形。若三个三角形都出现，它们已经覆盖六条边，所以第四个也出现；因此 $T=3$ 不可能。余下 $64-16-6-1=41$ 个图没有三角形。

从分布表直接算出

\mathbb ET=\frac{16+12+4}{64}=\frac12,\qquad \mathbb ET^2=\frac{16+24+16}{64}=\frac78,

故 $\operatorname{Var}T=7/8-1/4=5/8$ 。式 (3) 则给出

4\cdot\frac18\left(1-\frac18\right) +12\cdot\frac1{32}\cdot\frac12 =\frac7{16}+\frac3{16} =\frac58.

若错误地把四个三角形指示变量当作独立，只会得到 $7/16$ ，漏掉的 $3/16$ 正是共享边协方差的总贡献。

二阶矩正概率下界为

\mathbb P(T>0)\ge \frac{(1/2)^2}{7/8}=\frac27,

而精确概率是 $23/64$ 。下界不要求取等；它只用前两个矩，不读取完整分布。

同均值仍可越来越罕见

令 $X_n=n$ 的概率为 $1/n$ ，其余时候为零。则

\mathbb EX_n=1,\qquad \mathbb EX_n^2=n,\qquad \mathbb P(X_n>0)=1/n.

式 (1) 在这里恰好取等，却没有给出不随 $n$ 消失的概率。原因是相对方差为 $n-1$ ，完全不满足集中条件。若 $X$ 本身是成功概率 $q>0$ 的 Bernoulli 变量， $\mathbb EX=\mathbb EX^2=q$ ，(1) 同样取等。

所以“二阶矩有限”只是可使用公式的条件；要推出高概率结论，还必须控制它相对于均值平方的大小。

推论与应用

正概率、Paley–Zygmund 与相对集中

因为 $X=X1_{\{X>0\}}$ ，由Cauchy–Schwarz 不等式，

\mathbb EX \le\sqrt{\mathbb EX^2}\sqrt{\mathbb P(X>0)}.

平方后得到 (1)。再令 $\mu=\mathbb EX$ ，把期望按事件 $A=\{X\ge\theta\mu\}$ 分开：

\mu =\mathbb E[X1_{A^c}]+\mathbb E[X1_A] \le\theta\mu+\sqrt{\mathbb EX^2}\sqrt{\mathbb P(A)}.

移项并平方便得到 (2)。

对于相对集中，方差恒等式直接给出

\mathbb E\left[\left(\frac{X_n}{\mu_n}-1\right)^2\right] =\frac{\operatorname{Var}X_n}{\mu_n^2}\longrightarrow0.

或用Chebyshev 不等式写成显式概率界：

\mathbb P\!\left(\left|\frac{X_n}{\mu_n}-1\right|\ge\varepsilon\right) \le\frac{\operatorname{Var}X_n}{\varepsilon^2\mu_n^2}. \tag{4}

当 $X_n=0$ 时相对偏差等于一，所以相同估计也使 $\mathbb P(X_n=0)\to0$ 。

按共享边精确计算三角形方差

写

T=\sum_{A\in\binom{[n]}3}I_A,

其中 $I_A$ 指示 $A$ 的三条边全部出现。每个 $I_A$ 的均值为 $p^3$ ，方差为 $p^3-p^6$ 。展开平方或协方差双线性性得到

\operatorname{Var}T =\sum_A\operatorname{Var}I_A +2\sum_{\{A,B\}:\,A\ne B}\operatorname{Cov}(I_A,I_B),

第二个和按无序三角形对计数，因此前面保留因子二。

若 $|A\cap B|\le1$ ，两份三角形使用互不相交的边集合；底层边相互独立，故 $I_A,I_B$ 独立，协方差为零。若 $|A\cap B|=2$ ，二者恰好共享一条边，全部出现需五条不同边同时存在，于是

\mathbb E[I_AI_B]=p^5,\qquad \operatorname{Cov}(I_A,I_B)=p^5-p^6.

要计数后一类无序对，先选公共边，再从其余顶点中选两个不同的第三顶点：

\binom n2\binom{n-2}2=6\binom n4.

这个选择唯一恢复一对不同三角形，没有重复。乘上方差展开中的二，就得到 (3) 的系数 $12\binom n4$ 。若采用有序对求和，则应直接计 $12\binom n4$ ，不能再乘二。

固定密度下的极限

固定 $0<p<1$ ，将 (3) 除以 $\mu_n^2=(\binom n3p^3)^2$ ，得到精确表达式

\frac{\operatorname{Var}T}{\mu_n^2} = \frac{6(1-p^3)}{n(n-1)(n-2)p^3} +\frac{18(n-3)(1-p)}{n(n-1)(n-2)p}. \tag{5}

第一项是 $O(n^{-3})$ ，第二项是 $O(n^{-2})$ ，其中常数允许依赖固定的 $p$ 。故 (4) 对任意固定 $\varepsilon>0$ 都趋于零，同时给出均方收敛。两种常用归一化因此满足

\frac{T}{\binom n3}\longrightarrow p^3,\qquad \frac{6T}{n^3}\longrightarrow p^3

均方且依概率。第一种的均值恰为 $p^3$ ；第二种的均值为

\frac{n(n-1)(n-2)}{n^3}p^3,

与 $p^3$ 有有限规模偏差，但偏差趋于零，方差也趋于零。 $p=0$ 时密度恒为零； $p=1$ 时图恒为完全图，上述密度极限为一。这两个端点直接处理即可， $p=0$ 时不使用除以 $\mathbb ET$ 的公式。

这里的 $6T/n^3$ 正是图核的三角形同态密度。常值核 $W\equiv p$ 的积分为 $p^3$ ，与直接二阶矩计算吻合。但这一计算只控制三角形统计，不证明整个随机图在割距离下收敛，也不说明中心化后服从正态极限。

概率方法在一阶均值不足时引入二阶矩；一阶矩方法能把坏结构期望小于一转成好对象存在，二阶矩则进一步衡量候选对象的重叠依赖。随机满足性、分枝过程存活及阈值下界也常采用这种机制；若相对方差过大，可能需要改变计数变量或使用更强的相关性工具，而不能只重复计算均值。

参考资料

Yufei Zhao, Probabilistic Methods in Combinatorics, MIT 18.226，2024-06-18 更新，§4.1, pp. 37–41：二阶矩集中及三角形重叠协方差。讲义用渐近数量估计；本页进一步逐类计数得到精确组合系数。
Noga Alon and Joel H. Spencer, The Probabilistic Method, 4th ed., Wiley, 2016, Chapters 3–4：正概率下界、二阶矩和相关性论证。

形式陈述 ​

四顶点均匀随机图的全部三角形取值 ​

同均值仍可越来越罕见 ​

正概率、Paley–Zygmund 与相对集中 ​

按共享边精确计算三角形方差 ​

固定密度下的极限 ​