Finding a threshold with two moments

The two rungs below locate two thresholds by two different-looking arguments — a branching process for the giant, a count of isolated points for connectivity. They are the same argument, and stating it in general is what turns two results into a method.

The method is: count what the property needs, and then check that the count is not concentrated on rare cases. The first half is one line and gives half the answer; the second half is where the work is.

The first moment, which is free #

Let $X$ be the number of copies of some structure — triangles, say — in a random graph. Then

$$\Pr[X \ge 1] \le \mathbb{E}[X],$$

because a count taking whole values and having a small mean is usually zero. That is Markov’s inequality and it needs no assumption at all beyond non-negativity.

For triangles the expectation is immediate, and it uses only that expectations add whether or not the things being counted are independent — which is the property that makes the first moment free. There are $\binom{n}{3}$ triples and each is a triangle with probability $p^3$, so

$$\mathbb{E}[X] = \binom{n}{3}p^3 \approx \frac{(np)^3}{6}.$$

So with $p = c/n$ the expectation is about $c^3/6$, which does not depend on $n$ at all. Below $p = 1/n$ the expectation is small and triangles are rare; above it the expectation is large and — the first moment cannot say.

That asymmetry is the entire structure of the method. A small expectation proves absence; a large expectation proves nothing. Everything else in this rung is about repairing the second half.

Why a large expectation proves nothing #

The standard cautionary example is worth having, because the failure is not exotic.

Consider a random graph with $p$ fixed at $1/2$ and ask for a clique — a set of points all joined to each other — of size $2\log_2 n$. The expected number of such cliques tends to infinity, and it does not follow that one exists with high probability. The largest clique in such a graph is concentrated on two consecutive values near $2\log_2 n$, and finding one algorithmically is a famous open problem: nobody knows how to find a clique of size $(1+\varepsilon)\log_2 n$ in polynomial time, though almost every graph has one of nearly twice that size.

The general failure: a count can have a huge mean because it is enormous on a rare event and zero otherwise. A lottery has a large expected payout and pays nothing almost always.

What is needed is a bound on the variance, and Chebyshev’s inequality then gives

$$\Pr[X = 0] \le \frac{\mathrm{Var}[X]}{\mathbb{E}[X]^2}.$$

So if the variance is small compared with the square of the mean, the count is close to its mean and is in particular positive.

The second moment, for triangles #

The variance calculation is where the structure of the problem enters, and for triangles it is instructive.

Write $X = \sum_T I_T$ over triples $T$, with $I_T$ the indicator that $T$ is a triangle. Then

$$\mathrm{Var}[X] = \sum_{T, T'} \big(\Pr[I_T I_{T'}] - \Pr[I_T]\Pr[I_{T'}]\big),$$

and the terms are non-zero only when $T$ and $T'$ share an edge — triples sharing at most a vertex are independent, since they use disjoint sets of possible edges.

Two triples sharing an edge use five edges between them, so the joint probability is $p^5$ against $p^6$ for independent ones, and there are about $n^4$ such pairs. So the variance is of order $n^4p^5$, and the ratio to the mean squared is

$$\frac{n^4p^5}{(n^3p^3)^2} = \frac{1}{n^2p} ,$$

which tends to zero exactly when $np \to \infty$.

So above $p = 1/n$ triangles exist with high probability, matching the first moment’s bound below it. The threshold is at $p = 1/n$, and the two moments have bracketed it.

The calculation’s shape is worth extracting from its arithmetic. The variance was small because most pairs of triples are independent — only the ones sharing an edge contribute, and those are a vanishing fraction of all pairs. Whenever a count is a sum of many nearly-independent indicators, its variance is close to its mean, the ratio to the mean squared is about one over the mean, and the second moment succeeds automatically. The second moment is easy exactly when the features are spread out and hard exactly when they clump, and the calculation is a way of measuring the clumping.

The triangle is the right first example for a specific reason: its threshold is at $p = 1/n$, which is the same place as the giant component’s, and it is a completely different property. That coincidence is worth not over-reading. Two properties can share a threshold without being related, and the reason both sit at $1/n$ is that both are governed by counts of small structures against $n$ — the giant by the branching mean, the triangle by the expected count.

The general form is visible in the expectation. The expected number of copies of a structure with $v$ vertices and $e$ edges is about $n^v p^e$, so the threshold is at $p = n^{-v/e}$. For a triangle, $v = e = 3$ and that is $1/n$; for a four-cycle, $v = e = 4$ and it is again $1/n$; for a complete graph on four points, $v = 4$ and $e = 6$, giving $n^{-2/3}$ — a later threshold, since a denser structure is harder to find.

What makes a property have a threshold at all #

The two moments locate a threshold and do not establish that one exists, and the existence is a separate and much more general theorem.

A property is monotone when adding edges cannot destroy it: containing a triangle, being connected, having a giant component are all monotone. For such a property, Bollobás and Thomason proved in 1987 that a threshold always exists — a function $p^*(n)$ such that below any constant multiple of it the property fails with high probability and above any constant multiple it holds.

The theorem says nothing about where. It is an existence result of the kind that is worth having precisely because the location is what the moments compute — knowing that a threshold exists licenses the search for it, and before the theorem one could imagine a property whose probability oscillated as $p$ rose.

There is a sharper question with a stranger answer. Some thresholds are sharp — the probability moves from nearly zero to nearly one over a range of $p$ that is a vanishing fraction of $p^*$ — and some are coarse, moving over a constant multiple. Connectivity is sharp; containing a triangle is coarse, which the hero figure shows by moving over a factor of thirty in $p$.

Friedgut’s theorem characterises which: a monotone property has a coarse threshold only if it is approximable by the appearance of some bounded structure. Triangles are exactly that, and connectivity is not — a graph is disconnected because of an obstruction whose size grows with the graph, so no bounded structure captures it. That is a satisfying answer to a question one might have thought had no clean answer, and it is the sort of result an impossibility of another kind makes possible: knowing which properties are and are not local.

The method beyond graphs #

The two moments are not a graph technique, and the general shape is worth naming.

The probabilistic method proves an object with some property exists by showing a random object has it with positive probability — which establishes existence without constructing anything, and is often the only route available. The first moment supplies the standard version — if the expected number of bad features is less than one, some object has none — and it is how Erdős proved lower bounds on Ramsey numbers, which is a bound obtained without exhibiting anything and remains, seventy years later, the best known.

The second moment supplies the harder direction everywhere it is used: in number theory, where the number of prime factors of a random integer concentrates around $\log\log n$ by exactly this calculation; in the study of random constraint satisfaction, where the threshold for a random formula being satisfiable is bounded above by a first moment and below by a second.

And in every case the shape is the same. The first moment bounds the count from above and is one line. The second requires understanding which pairs of features are correlated, and that understanding is the actual content.

The asymmetry has a consequence for how such results are reported. A paper establishing a threshold usually states the two bounds separately, and the two are often proved in different decades: the first-moment bound arrives with the problem and the matching lower bound arrives when somebody works out the correlation structure. A gap between an easy upper bound and a hard lower bound is the normal state of a threshold problem, and closing it is what constitutes progress.

There is a subtlety in that formula worth flagging, since it is where the naive version of the method fails. The threshold for containing a structure $H$ is $n^{-1/m(H)}$ where $m(H)$ is the maximum, over all subgraphs of $H$, of the edge-to-vertex ratio. For a triangle every subgraph is sparser, so the maximum is the whole thing and the naive answer is right. For a structure containing a dense piece, the piece appears later than the whole would suggest, and the whole cannot appear before its piece does.

So the correct threshold is set by the densest sub-structure, and using the whole structure’s ratio gives an answer that is too early. That is the standard trap, and it is a good illustration of the general point: the first moment is easy and applying it to the wrong count is easy too.

Where the second moment is not enough #

Three situations defeat it, and knowing them is knowing the method’s boundary.

Strong correlations. When the features being counted overlap heavily, the variance is comparable with the mean squared and Chebyshev gives nothing. The clique example above is of this kind: large cliques overlap in large sub-cliques and the count is not concentrated.

Counts dominated by a few configurations. If the expected count is inflated by a rare event contributing enormously, the truth is that the property usually fails and the expectation is misleading. A refinement — condition on the rare event not happening, then apply the moments to what is left — often rescues it, and is the standard repair. It is also where most of the difficulty in modern threshold results sits, since choosing what to condition on is another modelling decision with no rule attached.

And properties with no natural count. Connectivity has no count of “connectivity witnesses”; the previous rung’s argument counts obstructions instead, and the moments are applied to those. Choosing what to count is a modelling decision and there is no general rule — which is why the method is a method rather than an algorithm, and why a hard threshold problem stays hard.

Comparing the two properties makes the method’s scope clear. Anything that can be counted can be thresholded, and the art is entirely in choosing the count.

For the triangle the natural count is the triangles. For the giant it is paths, or trees, of a given size — a component of size $k$ contains a spanning tree of size $k$, so counting trees bounds the probability from above, and the first moment gives the subcritical regime immediately. For connectivity the count is of obstructions, since there is nothing to count that connectivity requires the presence of.

Those three choices are three different modelling decisions and the method is indifferent between them. A count whose expectation crosses one at the right place, with features that are nearly independent, is what the method needs; finding one is the work.

What the pictures cannot show #

The variance is the whole content and no figure carries it. Both figures plot a measured probability against an expectation, which is the first-moment half of the argument. The second-moment half is a calculation about pairs of overlapping triples and produces no curve.

The dashed curve is an expectation capped at one and is not a probability. Capping it makes it comparable with the measured curve and the cap has no meaning: an expectation of three triangles does not mean a probability of one. Where the two curves agree, the agreement is Markov’s inequality being nearly tight; where they diverge, the divergence is the cap.

The measurement is a proportion over sixty samples. That is enough to trace a curve and not to resolve its behaviour near the threshold, which is where the two moments’ bounds are furthest apart.

The exact enumeration is at four and five points, where no threshold exists. It is drawn to show what the estimates approximate, and at that size the probability of a triangle is a polynomial with no interesting behaviour. The gap between what can be computed exactly and where the phenomenon lives is the whole reason the moment method exists.

And the thresholds are asymptotic. Every statement here is about $n$ tending to infinity, and the figures are at two hundred and four hundred points. What the second figure shows is that the shape is stable as the size grows, which is evidence and not the theorem.

Why the threshold for a triangle is coarse #

The contrast with connectivity is worth working out, because it makes the sharp-versus-coarse distinction concrete rather than definitional.

Above the threshold, the expected number of triangles is about $c^3/6$ where $c = np$. At $c=1$ that is a sixth; at $c = 2$, about one and a third; at $c=3$, four and a half. The count is Poisson-ish, so the probability of at least one triangle is roughly $1 - e^{-c^3/6}$: about fifteen per cent at $c=1$, seventy-four at $c=2$, ninety-nine at $c=3$.

The probability climbs from nothing to nearly everything over a factor of three in $p$, and no larger $n$ changes that, because the expectation does not depend on $n$ at all. That is a coarse threshold, and it is coarse precisely because a bounded structure appears in bounded expected numbers.

Connectivity is different because its obstruction count is $ne^{-c}$, which does depend on $n$: it crosses one over a range of $c$ of order one, which is a vanishing fraction of the threshold $\log n$. The same arithmetic, one quantity depending on the size and one not, and two qualitatively different transitions.

Where the ladder goes next #

This rung closes the ladder’s first pass: the transition observed, the giant located and sized, the second threshold separated from the first, and the general method set out here.

Named here as debts. Friedgut’s theorem, quoted above and not explained, which decides sharp against coarse. And the satisfiability threshold for random formulas, which is where the two-moment method has been pushed hardest and where the gap between the two bounds is still open.

Sideways, the concentration that turns a mean into a statement is the deviation bound, the counting of what a property needs is the same first-moment argument that proves Ramsey bounds, and the two thresholds this generalises are the previous rungs’.

What is worth carrying away #

An expectation gives one direction of a threshold for free and the other direction never, and knowing which is which prevents most of the mistakes in this area.

A small expected count proves the structure is absent. A large expected count proves nothing at all until the variance is controlled — and the variance is controlled exactly when the features being counted are nearly independent, which is a structural question about how they overlap.

The habit worth taking is to ask which pairs of the counted things are correlated. That single question is the second moment, it is where the difficulty of every such argument lives, and it usually identifies the obstruction when the method fails.

The corollary worth keeping is about how to read a failed second-moment argument. When the variance refuses to be small, that is rarely a sign that the structure is absent; it is usually a sign that the counted features cluster — that a few configurations account for most of the count — and the repair is to count something else whose copies overlap less.