From averaging to counting
The previous guide made existence cheap through averaging: if the expected value of some quantity is, say, at most c, then some outcome achieves at most c, because no random variable can sit strictly above its own mean everywhere. The first moment method is the disciplined form of that idea aimed at counting. You build a non-negative integer-valued count X — the number of monochromatic triangles, the number of bad edges, the number of copies of a fixed subgraph — and you read existence or non-existence straight off E[X]. The whole method rests on one elementary inequality and one identity you already own from Volume I.
The inequality is Markov's inequality specialised to integers: for a non-negative integer X, the event X >= 1 is the event X != 0, and P(X >= 1) <= E[X]. The contrapositive is the engine: if E[X] < 1, then P(X = 0) > 0, so an outcome with X = 0 must exist. That is the entire first moment principle — to prove an object with no bad parts exists, count the bad parts in a random object and show their average count is below one. The identity that makes E[X] computable is linearity of expectation: write X as a sum of indicators X = sum over i of 1_{A_i}, and then E[X] = sum over i of P(A_i), with no independence required.
First moment at work: Ramsey, and then deletion
The cleanest showcase is the Ramsey number lower bound. Colour each edge of the complete graph on N vertices red or blue independently with probability 1/2. Let X count the monochromatic copies of the complete graph on k vertices. By linearity, E[X] = C(N, k) times 2 times 2^(-C(k,2)), since each of the C(N,k) candidate k-sets is all-red or all-blue with probability 2 times 2^(-C(k,2)). If this expectation is below 1, some colouring has X = 0 — a colouring with no monochromatic k-clique — which says the Ramsey number R(k,k) > N. Optimising N gives R(k,k) > (1 + o(1)) (k / (e sqrt 2)) 2^(k/2), a bound from 1947 that, astonishingly, no explicit construction has beaten in the leading constant since.
Often the bald first moment is slightly too crude: E[X] sits a little above 1, so you cannot conclude X = 0 anywhere. The deletion method (also called alteration) rescues you with a second move. Pick the random object, accept that it has a few bad parts, and then surgically remove one vertex or element per bad part to destroy them all. What survives is a clean object whose size is the original size minus the number of deletions, and you bound the expected number of deletions by E[X]. The deletion method thus proves the existence of a large clean structure even when a perfectly clean one of full size is too much to ask.
- Sample the random object (a 2-colouring, a random graph, a random subset) and let X count the bad parts.
- Compute E[X] by linearity as a sum of P(bad part i appears) — no independence needed.
- Delete one element per bad part; the surviving object is clean, with expected size at least (initial size) minus E[X].
- Some outcome meets the expectation, so a clean object of that size exists — choose the initial size to make the surviving size as large as you can.
The second moment method: from positive expectation to positive probability
Now suppose E[X] is large and you want to conclude not just that X can be positive but that X > 0 with high probability — for instance, that a random graph almost surely contains a given subgraph. A large mean is not enough on its own: a lottery has a positive expected payoff yet pays nothing almost always, because all its mass is a tiny chance of a huge value. The cure is to control the spread. The second moment method uses the variance to rule out that lottery-like behaviour, via Chebyshev's inequality applied to the event X = 0.
The key estimate is short: if X = 0 then X deviates from its mean by the full E[X], so by Chebyshev P(X = 0) <= P(|X - E[X]| >= E[X]) <= Var(X) / E[X]^2. So whenever the variance is small relative to the square of the mean — that is, Var(X) = o(E[X]^2) — the probability that X vanishes tends to zero, and X > 0 with high probability. The ratio Var(X) / E[X]^2 is the whole game; it is exactly the squared coefficient of variation, the dimensionless measure of how concentrated the count is around its average.
X = sum_i 1_{A_i} a count of indicator events
E[X] = sum_i P(A_i) (linearity, no independence)
Var(X) = sum_i Var(1_{A_i}) + sum_{i != j} Cov(1_{A_i}, 1_{A_j})
P(X = 0) <= Var(X) / E[X]^2 (second moment / Chebyshev)
=> if Var(X) = o(E[X]^2) then X > 0 with high probabilityComputing Var(X) is where dependence finally costs you. Writing X = sum of indicators and expanding, Var(X) = sum of Var(1_{A_i}) plus sum over ordered pairs i != j of Cov(1_{A_i}, 1_{A_j}), by the bilinearity of covariance you met in Volume I. The diagonal terms are harmless; the off-diagonal covariance terms are the entire difficulty, and they are positive exactly when two bad parts tend to co-occur. The second moment method works precisely when those correlations are weak — when knowing one event happened barely raises the chance of another — which is why it is the natural partner of sparse, near-independent random structures.
Both moments together: thresholds in the random graph
The two methods become a single instrument when you study how a property switches on as a parameter grows. In the Erdős-Rényi random graph G(n, p), each of the C(n,2) edges is present independently with probability p, and we ask: for which p does a fixed subgraph H appear? Let X = the number of copies of H in G(n, p). The first moment gives the upper side: if E[X] -> 0 then by Markov X = 0 with high probability, so H is almost surely absent. The second moment gives the lower side: if E[X] -> infinity and Var(X) = o(E[X]^2), then X > 0 with high probability, so H almost surely appears. The crossover value of p is the threshold.
For a balanced subgraph H with v vertices and e edges, E[X] is of order n^v p^e, which crosses 1 near p = n^(-v/e). The subtle point is that the threshold is governed not by H itself but by its densest subgraph: the exponent that matters is the maximum of e(H') / v(H') over subgraphs H', the maximum subgraph density m(H), and the threshold sits at p = n^(-1/m(H)). The reason is exactly the covariance computation above — copies of H that share a dense common piece are the strongly correlated pairs that can blow up Var(X), and the densest subgraph is where that danger is greatest. This is the canonical example of a monotone property threshold.
Paley-Zygmund, the expectation threshold, and where this leads
Chebyshev is the textbook route to the lower bound, but there is a sharper and often more convenient tool with the same two ingredients. The Paley-Zygmund inequality says that for a non-negative X and any 0 <= t <= 1, P(X >= t E[X]) >= (1 - t)^2 times E[X]^2 / E[X^2]. Setting t -> 0 gives P(X > 0) >= E[X]^2 / E[X^2], a clean lower bound on the probability of positivity directly in terms of the first two moments. When the second moment is comparable to the square of the first, this probability is bounded away from zero — and a tightened version recovers the high-probability conclusion of the second moment method. It is the natural anti-concentration companion to the concentration inequalities of the next rung.
Both methods raise a single nagging question: how tight is the first moment as a predictor of thresholds? The first moment gives a necessary condition for a property to appear — E[X] must at least not vanish — and the heuristic that this necessary condition is also essentially sufficient is the content of the celebrated expectation-threshold conjecture of Kahn and Kalai. It posits that the true threshold for any increasing property lies within a logarithmic factor of the simple-to-compute expectation threshold. This was open for two decades and was finally proved (the Park-Pham theorem, 2022), a striking confirmation that first-moment intuition is rarely far wrong. Be honest, though: the gap really is a logarithmic factor, not zero.
When the events are sparse but not negligibly correlated, the second moment is too blunt — the off-diagonal covariances pile up and the bound dissolves. The remaining guides of this rung are exactly the upgrades. When the dependencies are local, the Lovász Local Lemma (next guide) certifies positive probability even when the union bound and first moment both fail. When you want sharp tail control on X rather than just P(X = 0), Janson's inequality and the martingale method of Azuma take over. And when you want the full limiting distribution of a sparse count — a Poisson limit, say — that is Stein-Chen in the final guide. The two moments are the foundation those all build on.