Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs

Statement

Paley–Zygmund inequality. Let $Z\ge 0$ be a random variable with $0<\mathbb E[Z^2]<\infty$. Then for every $\theta\in[0,1]$, $$\mathbb P(Z > \theta\,\mathbb E[Z]) \;\ge\; (1-\theta)^2\,\frac{(\mathbb E[Z])^2}{\mathbb E[Z^2]}.$$ (Paley & Zygmund, "On some series of functions, (3)," *Math. Proc. Cambridge Philos. Soc.*, 1932; en.wikipedia.org/wiki/Paley–Zygmund_inequality.) Proof sketch: split $\mathbb E[Z]=\mathbb E[Z\mathbf 1_{Z\le\theta\mathbb EZ}]+\mathbb E[Z\mathbf 1_{Z>\theta\mathbb EZ}]$; the first term is $\le\theta\mathbb E[Z]$, and the second is bounded via Cauchy–Schwarz by $\sqrt{\mathbb E[Z^2]\,\mathbb P(Z>\theta\mathbb EZ)}$; rearranging gives the bound.

Chebyshev / second-moment corollary used for existence (Yufei Zhao, "Probabilistic Methods in Combinatorics," Ch. 4, yufeizhao.com/pm/4.pdf, Thm 4.1.5, Cor 4.1.7–4.1.8, read in full). For any random variable $X$ with $\mu=\mathbb E X$, $\mathrm{Var}\,X=\mathbb E[X^2]-(\mathbb E X)^2$: $$\mathbb P(X=0)\;\le\;\mathbb P(|X-\mu|\ge\mu)\;\le\;\frac{\mathrm{Var}\,X}{(\mathbb E X)^2}.$$ Hence: if $\mathbb E X>0$ and $\mathrm{Var}\,X = o((\mathbb E X)^2)$, then $X>0$ and $X\sim\mathbb E X$ with high probability (whp), i.e. $X$ is not just positive but concentrated near its mean. This is exactly the $\theta\to 0$, $Z=X$ case of Paley–Zygmund combined with $\mathbb E[X^2]=\mathrm{Var}\,X+(\mathbb E X)^2$; the two formulations (Paley–Zygmund vs. Chebyshev-on-$X$) are algebraically interchangeable and both are called "the second moment method" in the literature.

Facts

- Origin of the inequality: R. E. A. C. Paley, A. Zygmund, "On some series of functions, (3)," *Math. Proc. Cambridge Philos. Soc.* 28 (1932). Originally about lacunary Fourier series, not combinatorics. - Origin of the combinatorial technique: predates Paley–Zygmund's explicit combinatorial use. P. Turán (1934), "On a Theorem of Hardy and Ramanujan," *J. London Math. Soc.*, gave the first celebrated second-moment application in number theory: an elementary re-proof of the Hardy–Ramanujan theorem (that $\omega(n)$, the number of distinct prime factors of $n$, is normally $\sim\log\log n$) by bounding $\sum_{n\le x}(\omega(n)-\log\log x)^2 \ll x\log\log x$ — i.e. showing the *variance* of $\omega(n)$ is small compared to $(\log\log x)^2$, forcing concentration. This "Turán sieve" is historically the archetype of the method, predating its systematic use in random graph theory. - Adoption in random graph theory: P. Erdős, A. Rényi, "On the evolution of random graphs," *Publ. Math. Inst. Hungarian Acad. Sci.* 5 (1960) 17–61, is the founding paper of the field and uses first/second-moment computations to locate thresholds (e.g. for the giant component, connectivity, perfect matchings) in $G(n,p)/G(n,m)$. - Standard modern textbook treatment: N. Alon, J. H. Spencer, *The Probabilistic Method* (Wiley), Ch. 4, "The Second Moment," is the most commonly cited canonical reference (title/chapter existence corroborated via WebSearch, not independently re-read here). - Worked example, $G(n,p)$ triangle threshold (Zhao, Thm 4.1.11, read in full): let $X$ = number of triangles. $\mathbb E X\asymp n^3p^3$. First moment alone (Markov) only shows $X=0$ whp when $np\to 0$ but says nothing when $np\to\infty$ (a nonzero mean is consistent with $X$ being usually $0$ and rarely huge). Computing $\mathrm{Var}\,X$ via pairwise covariances of the $\binom n3$ indicator variables gives $\mathrm{Var}\,X = O(n^3p^3)+O(n^4p^5) = o(n^6p^6)=o((\mathbb E X)^2)$ whenever $np\to\infty$, so $X>0$ whp — establishing $1/n$ as the sharp threshold for triangle-containment. - Bollobás's general theorem (B. Bollobás, 1981; stated as Thm 4.2.10 in Zhao's notes, proof read in full): for any fixed graph $H$, let $m(H)=\max_{H'\subseteq H} e_{H'}/v_{H'}$ (max edge/vertex density over subgraphs). Then $p=n^{-1/m(H)}$ is the threshold for $G(n,p)$ to contain a copy of $H$. The proof is a direct second-moment computation using a "dependency-graph" variance bound (Zhao's Lemma 4.2.4: if $X=\sum X_i$ counts occurrences of a pattern and $\Delta^*=\max_i\sum_{j\sim i}\mathbb P(A_j\mid A_i)=o(\mathbb E X)$, then $X>0$ and $X\sim\mathbb E X$ whp). **Crucially, the threshold is governed by the *densest subgraph* of $H$, not $H$ itself** — Zhao's Example 4.2.6 shows a graph $H$ (a $K_4$ with a pendant edge) whose own edge count would predict threshold $n^{-5/7}$, but the true threshold is $n^{-2/3}$ (that of its densest subgraph $K_4$), because a naive second-moment attempt on $X_H$ directly fails: the covariance term from two copies of $H$ overlapping in a $K_4$ dominates and is *not* $o((\mathbb E X_H)^2)$ in that regime. This is the canonical illustration that the second moment method can fail if applied to the wrong random variable, and the fix (count the densest sub-object, or otherwise restrict to a well-spread/low-correlation family) is itself part of the reusable technique. - Number-theoretic Erdős application: Erdős & Moser (1956, [Er56]) proved the classical lower bound for the distinct-subset-sums problem ($A\subseteq\{1,\dots,N\}$, all subset sums of $A$ distinct $\Rightarrow N\gg 2^n$) via the second-moment/variance method applied to the random signed sum $X=a_1\varepsilon_1+\cdots+a_n\varepsilon_n$ ($\varepsilon_i=\pm1$ i.i.d. fair coins): bounding $\mathrm{Var}(X)$ forces many of the $2^n$ sign patterns to land near $0$, and dissociation (all subset sums distinct) then forces $N\gg 2^n/\sqrt n$. See Erdős #1 — distinct subset sums need N ≫ 2^n. The current-record constant $\sqrt{2/\pi}$ (Elkies–Gleason, confirmed by Dubroff–Fox–Xu, arXiv:2006.12988) sharpens the same variance-method skeleton to an *exact* bound $N\ge\binom{n}{\lfloor n/2\rfloor}$. - Cochromatic-number application: A. Heckel, "The difference between the chromatic and the cochromatic number of a random graph," arXiv:2409.17614 (answering an Erdős–Gimbel c.1991 question for $G(n,1/2)$), uses a Paley–Zygmund-based second-moment argument (her Prop. 5, transferred to cochromatic colour-counts via a $2^k$ clique/independent-set choice factor in Prop. 6) to show concentration/existence of near-optimal cocolourings, for ~95% of values of $n$. See Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)?. - Modern "second-moment"-flavoured proof of the spread lemma: E. Mossel, J. Niles-Weed, N. Sun, I. Zadik, "A second moment proof of the spread lemma," arXiv:2209.11347, gives a fourth independent proof (via a Bayesian-inference recasting) of the spread lemma underlying the Alweiss–Lovett–Wu–Zhang sunflower bound and the Frankston–Kahn–Narayanan–Park fractional Kahn–Kalai threshold theorem — evidence the method generalizes beyond simple subgraph-counting to deep modern threshold results. See R-spread set families (ALWZ/Rao's central reduction device), Kahn–Kalai expectation-threshold vs. threshold-probability conjecture (Park–Pham theorem). - Weaker dependency regimes: when a random variable is a sum of *many weakly correlated* indicators (rather than few strongly correlated ones — e.g. Hardy–Ramanujan's $\omega(n)$ summed over all primes $p\le x$), the direct covariance-sum approach still works but requires more delicate estimates (Turán sieve-type bounds); Zhao's notes flag this regime (§4.5, Hardy–Ramanujan) as needing extra care versus the "few dependencies" bounded-$\Delta^*$ setup that suffices for fixed-subgraph thresholds.

Technique

When it applies: whenever you want to prove a *nonnegative, integer- (or real-) valued* random variable $X$ — typically a count of copies of some structure (triangles, cliques, a fixed subgraph $H$, sunflowers, colourings, subset sums landing in an interval, etc.) in a randomly generated object — is positive with high probability, or more strongly, is concentrated around its mean. It is the natural second step after a first-moment computation ($\mathbb E X$): the first moment alone only ever gives an *upper* bound on $\mathbb P(X>0)$ via Markov's inequality (useful for $0$-statements, i.e. proving non-existence when $\mathbb E X\to 0$), and can *never* by itself prove existence, because a large mean is consistent with $X$ being usually $0$ but occasionally huge. The second moment method supplies the matching *lower* bound on $\mathbb P(X>0)$ (a $1$-statement / existence proof) by additionally bounding the variance.

Why it works (the mechanism): Chebyshev's inequality applied to $X$ says $X$ is unlikely to be very far from its mean $\mu=\mathbb E X$, with "far" measured in units of the standard deviation $\sigma=\sqrt{\mathrm{Var}\,X}$. If $\sigma \ll \mu$ (i.e. $\mathrm{Var}\,X=o(\mu^2)$), then "$X=0$" is a deviation of a full $\mu/\sigma\to\infty$ standard deviations from the mean, hence has probability $\to 0$. Equivalently (Paley–Zygmund), a nonnegative random variable with small *relative* variance ($\mathbb E[X^2]/(\mathbb E X)^2$ close to $1$) cannot concentrate its mass near $0$ without violating the first-moment identity $\mathbb E X=\mu$ — it is forced to actually be near $\mu$ on a set of probability close to $1$. The whole method thus reduces an existence question to a pure computation: bound $\mathbb E X$ (linearity of expectation — easy) and $\mathrm{Var}\,X=\sum_i\mathrm{Var}\,X_i+2\sum_{i<j}\mathrm{Cov}[X_i,X_j]$ when $X=\sum_i X_i$ is written as a sum of indicators (covariance is bilinear, no independence needed) — and check the ratio $\mathrm{Var}\,X/(\mathbb E X)^2\to 0$.

The reusable recipe (synthesized from Zhao Ch. 4, worked in full on the triangle/fixed-subgraph case): 1. Write the target quantity as $X=\sum_{i=1}^m X_i$, indicator variables for $m$ "potential occurrences" of the structure (e.g. one indicator per $|V(H)|$-subset of vertices for subgraph-counting, or per sign pattern for subset-sum problems). 2. Compute $\mathbb E X=\sum_i\mathbb P(A_i)$ by linearity — routine. 3. Bound $\mathrm{Var}\,X\le \mathbb E X + (\mathbb E X)\Delta^*$ where $\Delta^*=\max_i\sum_{j\sim i}\mathbb P(A_j\mid A_i)$ sums conditional probabilities only over *dependent* pairs $j\sim i$ (independent pairs contribute $0$ covariance) — this is the "few dependencies" setup (Zhao's Lemma 4.2.4); it requires identifying which pairs of potential occurrences can share structure (e.g. share $\ge 2$ vertices) and bounding how many such pairs exist and how correlated they are. 4. If $\mathbb E X\to\infty$ and $\Delta^*=o(\mathbb E X)$, conclude $X>0$ and $X\sim \mathbb E X$ whp. 5. Watch for the "densest subgraph" trap (Bollobás's theorem / Zhao Example 4.2.6): if $X$ counts a composite structure $H$ with a denser sub-pattern $H'\subsetneq H$, the covariance from two copies of $H$ overlapping exactly on $H'$ can dominate and break step 3/4 even though $\mathbb E X\to\infty$; the fix is to identify $m(H)=\max_{H'\subseteq H}\rho(H')$ and use *that* density to locate the true threshold (Bollobás 1981). 6. When dependencies are not "few but strong" but rather "many but weak" (e.g. summing indicators over primes for $\omega(n)$), the same variance formula still applies but the covariance-sum bookkeeping is more delicate (Turán-sieve style estimates); the underlying Chebyshev step is unchanged.

What it does NOT give: only $\Theta(1)$-order concentration / whp existence — it does not by itself give exponential-tail bounds (those need Chernoff/Azuma/martingale or Janson-type inequalities, which is why $G(n,p)$ courses typically introduce second-moment *before* those sharper tools), nor does it give a *sharp threshold* (exact location up to $(1+o(1))$) without extra work, nor does it handle highly non-monotone / adversarially anti-correlated structures well.

Related

- R-spread set families (ALWZ/Rao's central reduction device) — the $r$-spread/hitting lemma underlying the ALWZ sunflower bound and Kahn–Kalai thresholds has an alternative proof via a Bayesian recasting of the second moment method (Mossel–Niles-Weed–Sun–Zadik, arXiv:2209.11347). - Kahn–Kalai expectation-threshold vs. threshold-probability conjecture (Park–Pham theorem) — the modern, black-box replacement for many bespoke second-moment threshold arguments: once an expectation-threshold estimate $q(\mathcal F)$ is known, Park–Pham's theorem gives the true threshold up to a log factor "for free," without a custom variance computation. - Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — a structurally distinct technique (Shannon-entropy/coding-theoretic) that in several cases (sunflower bound, spread lemma) proves the *same* results as the second moment method via a different route, evidence of deep proof-technique redundancy in this area. - Erdős #1 — distinct subset sums need N ≫ 2^n — Erdős–Moser's original 1956 second-moment lower bound $N\gg 2^n/\sqrt n$ for the distinct-subset-sums problem, later sharpened to the exact bound $N\ge\binom n{\lfloor n/2\rfloor}$ (Dubroff–Fox–Xu, arXiv:2006.12988) via the same variance-method skeleton. - Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? — Heckel's Paley–Zygmund-based cochromatic-colouring concentration argument (arXiv:2409.17614), answering the Erdős–Gimbel chromatic-vs-cochromatic question for ~95% of $n$. - Harris–FKG correlation inequality for increasing/decreasing events (random graphs, percolation) — a complementary correlation-inequality technique often combined with second-moment arguments (e.g. in the Heckel/Steiner cochromatic-number line of work) to compare monotone random-graph quantities.