Second Moment Method

The second moment method uses variance to prove that a non-negative random variable is positive with high probability. While the first moment method shows $\Pr[X > 0] > 0$ from $\mathbb{E}[X] > 0$ does not follow, the second moment method bridges this gap.

Statement

Theorem7.1Second Moment Method (Paley-Zygmund)

Let $X$ be a non-negative random variable with $\mathbb{E}[X] > 0$ . Then: $\Pr[X > 0] \geq \frac{(\mathbb{E}[X])^2}{\mathbb{E}[X^2]}.$ Equivalently, using $\operatorname{Var}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2$ : $\Pr[X = 0] \leq \frac{\operatorname{Var}(X)}{(\mathbb{E}[X])^2}.$

Proof

By the Cauchy-Schwarz inequality applied to $X \cdot \mathbf{1}_{X > 0}$ : $(\mathbb{E}[X])^2 = (\mathbb{E}[X \cdot \mathbf{1}_{X > 0}])^2 \leq \mathbb{E}[X^2] \cdot \Pr[X > 0].$ Rearranging gives the result. $\square$

■

Applications

ExampleClique Threshold in $G(n, p)$

For fixed $k \geq 3$ , the threshold for $G(n, p)$ to contain a copy of $K_k$ is $p = n^{-2/(k-1)}$ . Let $X$ count copies of $K_k$ . Then $\mathbb{E}[X] = \binom{n}{k} p^{\binom{k}{2}} \asymp n^k p^{k(k-1)/2}$ . For $p \gg n^{-2/(k-1)}$ , $\mathbb{E}[X] \to \infty$ , and the second moment method shows $\Pr[X > 0] \to 1$ by bounding $\mathbb{E}[X^2] / (\mathbb{E}[X])^2 \to 1$ .

RemarkControlling Correlations

The key challenge in the second moment method is bounding $\mathbb{E}[X^2] = \sum_{i,j} \mathbb{E}[X_i X_j]$ , where $X = \sum_i X_i$ is a sum of indicator variables. The "diagonal" terms ( $i = j$ ) contribute $\mathbb{E}[X]$ , while the off-diagonal terms require careful analysis of pairwise correlations.

ExampleConnectivity of $G(n, p)$

The sharp threshold for connectivity of $G(n, p)$ is $p = \frac{\log n}{n}$ . Let $X$ be the number of isolated vertices. Then $\mathbb{E}[X] = n(1-p)^{n-1} \sim ne^{-pn}$ . For $p = \frac{\log n + c}{n}$ , $\mathbb{E}[X] \to e^{-c}$ . The second moment method confirms $X$ is approximately Poisson, so $\Pr[X = 0] \to e^{-e^{-c}}$ .

Theorem7.2Chebyshev's Inequality

For any random variable $X$ with finite variance and $t > 0$ : $\Pr[|X - \mathbb{E}[X]| \geq t] \leq \frac{\operatorname{Var}(X)}{t^2}.$ This is the simplest tool derived from the second moment and suffices when variance is small relative to the square of the expectation.