THE SECOND MOMENT METHOD,

CONDITIONING AND APPROXIMATION

Svante Janson

Abstract. The second moment method has been fruitfully combined with conditioning by several authors, for example Robinson and Wormald [7],

[8] and Frieze and Janson [2]. We try to give a general exposition of this method, and of its relation to approximations of random variables by simpler variables. We discuss several examples where the method has been used in different forms.

1. The second moment method

One of the classical methods to show the existence (with large probability) of certain substructures in a random graph is the second moment method. We can describe a general version of the method as follows.

Consider some random combinatorial structure G. In order to study the existence of a certain type of substructure (for example, a Hamilton cycle, a perfect matching, an induced C_{4}, …), we let X = X(G) be the number of such substructures in G. Thus X is a random variable taking non-negative integer values, and the problem is to estimate P(X > 0). We assume that P(X > 0) > 0 (otherwise the substructures never appear) and that E X^{2} < ∞ (in fact, we usually study finite random structures, where X is bounded).

Typically, we are interested in asymptotic results. We consider a sequence of such random structures G (a more precise notation would be G_{n}, but we will usually ignore the subscript n) and want to show P(X > 0) → 1. The second moment method asserts that this follows if we can show

Var X/(E X)^{2} → 0  (1)

or, equivalently,

E X^{2}/(E X)^{2} → 1.  (1′)

Typeset by AMS-TEX

Supported by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine

Research carried out during a visit to the IMA, Minneapolis

The proof is immediate by Chebyshev’s inequality:

P(X = 0) ≤ \frac{Var X}{(E X)^{2}} = \frac{E X^{2}}{(E X)^{2}} − 1.  (2)

Alternatively, the Cauchy–Schwarz inequality gives

(E X)^{2} = (E(XI(X > 0)))^{2} ≤ E X^{2} P(X > 0)

and thus

P(X = 0) = 1 − P(X > 0) ≤ 1 − \frac{(E X)^{2}}{E X^{2}} .  (3)

The bound in (3) is better than the bound in (2), but for our purposes both bounds are equally powerful.

Note that (1) is much stronger than the conclusion P(X > 0) → 1. In fact, (1) can be written Var(X/ E X) → 0 or E(X/ E X − 1)^{2} → 0, i.e.

X/ E X ⟶^{L^{2}} 1.  (4)

In particular, by Chebyshev’s inequality again,

X/ E X ⟶^{p} 1;  (5)

i.e., for every ε > 0,

P((1 − ε) E X < X < (1 + ε) E X) → 1.  (6)

Hence, the second moment method is applicable only when X can be well approximated (in the sense of (4)–(6)) by the non-random value E X; in other words, the distribution of X has to be (asymptotically) concentrated at a single value.

2. Conditioning

There are many cases where the second moment method fails because (4)–(6) do not hold; for example, X/ E X may converge in distribution to a non-degenerate random variable. In such cases, the method may be combined with conditioning as follows.

Let us choose another random variable Y = Y (G); Y does not have to be real-valued, for example, Y may be a sequence (Y^{(1)}, Y^{(2)}, …) of real random variables. For simplicity we assume that Y is discrete, i.e. Y assumes only a countable number of values. (For the approach to be useful, we also want Y to be simpler than X in some sense.) Two examples, considered again later, are Y = the number of edges in a random graph G(n, p), and Y = (d_{1}, …, d_{n}), where d_{i} is the degree of vertex i in a random graph or hypergraph.

Recall that the conditional expectation E(X | Y) is a random variable which is a function of Y; more precisely, it equals g(Y), where the function g is defined by g(y) = E(X | Y = y) whenever P(Y = y) > 0. Similarly, the conditional variance is the random variable

Var(X | Y) = E((X − E(X | Y))^{2} | Y ) = E(X^{2} | Y) − E(X | Y)^{2}.

We can now apply (2) after conditioning on Y (i.e., conditioning on Y = y for each y) and obtain

P(X = 0 | Y) ≤ \frac{Var(X | Y)}{E(X | Y)^{2}}  (7)

whenever E(X | Y) > 0. (Recall that both sides of (7) are random variables.)

For convenience, we make the right hand side of (7) everywhere defined by assigning an arbitrary value in [0, ∞] to it when E(X | Y) = 0 (in which case it is of the form 0/0).

Theorem 1. Suppose that P(E(X | Y) = 0) → 0 and

Var(X | Y)/ E(X | Y)^{2} ⟶^{p} 0.  (8)

Then P(X = 0) → 0.

Proof. Since conditional probabilities are bounded by 1, (7) can be rewritten

P(X = 0 | Y) ≤ min(1, Var(X | Y)/ E(X | Y)^{2}) + I(E(X | Y) = 0) (9)

which by taking expectations yields

P(X = 0) ≤ E min(1, Var(X | Y)/ E(X | Y)^{2}) + P(E(X | Y) = 0). (10)

The first term on the right hand side tends to 0 by (8) and dominated convergence, while the second tends to 0 by assumption. □

The condition (8) may be rewritten

E(X^{2} | Y)/ E(X | Y)^{2} ⟶^{p} 1  (11)

or

P(Var(X | Y) > ε E(X | Y)^{2}) → 0,  for every ε > 0.  (12)

We may also write it as

Var(\frac{X}{E(X | Y)} | Y ) ⟶^{p} 0  (13)

and it follows easily that the conditions of Theorem 1 imply

\frac{X}{E(X | Y)} ⟶^{p} 1  (14)

or, for every ε > 0,

P((1 − ε) E(X | Y) < X < (1 + ε) E(X | Y)) → 1.  (15)

Hence the conditional second moment method is applicable only when X can be well appproximated (with a relative error that is small in probability) by a function of Y. The converse is not necessarily true, since variables may converge in probability without converging in L^{2}, but we do not expect this to happen in practical applications, and thus we expect Theorem 1 to be applicable whenever X is well approximated by some function g(Y). (We may then take g(Y) = E(X | Y), but some approximation of E(X | Y) may be simpler.) This should be compared to the unconditional second moment method described above, which applies only when the approximation can be chosen as a “constant”. (We put “constant” in inverted commas, since we really consider a sequence G = G_{n} of random structures and everything, including the function g and this “constant”, may depend on the parameter n.)

We also remark that when the conditional second moment method is applicable, it typically also yields the asymptotic distribution of X exactly when the unconditional second moment method is not applicable. In fact, we have just seen that then X/g(Y) ⟶^{p} 1 for some variable g(Y) which is not (asymptotically) degenerate. Hence, if for example g(Y)/ E g(Y) or a_{n} log g(Y) − b_{n} (for some constants a_{n}, b_{n}) converges to some (nondegenerate) distribution, we obtain the same result for X. (This is closely related to the projection methods for obtaining asymptotic distributions, where, however, one often considers approximations of a variable X by a linear function g(Y) only.)

3. Applications

We have so far discussed the theoretical limits of the method. For practical applications, we also have to be able to verify the hypotheses of the theorem. There are at least three different methods to do this. We describe these methods below, and illustrate them by examples where they have been used by various authors (at least implicitly; the descriptions below are reformulations of the arguments in the original references). The methods often lead to long and non-trivial combinatorial calculations, which we omit here; see the references given in the examples below.

I. The first possibility is a straightforward computation of E(X | Y) and E(X^{2} | Y).

Example 1. Janson [3] considered the number of spanning subtrees of the random graph G(n, p), with p constant and n → ∞; let us denote this number by X. It is well-known that P(X > 0) → 1, but the objective in [3] was to find the asymptotic distribution. This was achieved using the argument above, with Y being the number of edges in G(n, p). Note that conditioning on Y = m is the same as considering the random graph G(n, m); hence E(X | Y = m) and E(X^{2} | Y = m) can be evaluated as the first two moments of the number of spanning trees in G(n, m). These can be estimated rather easily, see Moon [6], which leads to an asymptotic log-normal distribution of X.

Example 2. Consider the random hypergraph G(ns, m; s) with ns vertices and m random hyperedges consisting of s vertices each. Frieze and Janson [2] showed that if s ≥ 2 is fixed, and n → ∞ with m/n^{4/3} → ∞, then the random hypergraph contains a perfect matching (i.e., a covering of the vertex set by n disjoint hyperedges) with probability tending to 1. The proof is based on Theorem 1, letting X be the number of perfect matchings and Y = (d_{1}, …, d_{ns}), where d_{i} is the degree of vertex i, i.e., the number of hyperedges containing i. Actually, the computations are performed for a slightly different model, namely a random multihypergraph where the hyperedges are obtained by sampling ms vertices with replacement and then grouping them s by s; this allows both multiple hyperedges and defect hyperedges with less than s distinct vertices, but the distribution of Y (which becomes multinomial) and the calculation of E(X | Y) and E(X^{2} | Y) are much simplified.

It turns out that if m ≫ n^{3/2}, then E(X | Y) is concentrated at E X, and the unconditional second moment method applies, see Schmidt and Shamir [9]. When m is smaller, this is no longer true and we need the conditional version. Note also that the proof requires m ≫ n^{4/3}, although there is no reason to believe that this is necessary for the result (presumably m ≫ n log n is enough, as it is for s = 2). The discussion above gives (or at least suggests) the explanation that the number of perfect matchings is well approximated by a function of the vertex degrees only when m ≫ n^{4/3} (and by a constant when m ≫ n^{3/2}); for smaller m the number depends significantly also on other properties of the hypergraph, but it may of course still be non-zero.

In principle it seems possible to improve the result by conditioning on more parameters beside the vertex degrees, cf. Example 4 below, but it seems hopeless to perform the necessary computations.

II. It is often complicated to calculate the conditional variance Var(X | Y) or E(X^{2} | Y). A possible alternative is to use an analysis of variance argument as follows, which only requires calculation of the conditional expectation E(X | Y) and the unconditional variance Var X. This is essentially the method invented by Robinson and Wormald [7], [8], see also Cooper, Frieze, Molloy and Reed [1] and Janson [5].

By definition, the terms in the decomposition

X = (X − E(X | Y)) + E(X | Y)  (16)

are orthogonal, and

Var X = Var(X − E(X | Y)) + Var(E(X | Y))
= E(X − E(X | Y))^{2} + Var(E(X | Y))
= E(Var(X | Y)) + Var(E(X | Y)).  (17)

Recall that the model G, and thus also the variables X and Y, depends on a parameter n. The o below should be interpreted as n → ∞.

Theorem 2. If

Var X = Var(E(X | Y)) + o((E X)^{2}),  (18)

and

lim_{ε→0} lim sup_{n→∞} P(E(X | Y) < ε E X) = 0,  (19)

then P(X = 0) → 0.

Proof. For every ε > 0 and δ > 0,

P(Var(X | Y)/ E(X | Y)^{2} > ε)

≤ P(Var(X | Y)/(E X)^{2} > εδ^{2}) + P(E(X | Y) < δ E X). (20)

Moreover, by (18) and (17), E(Var(X | Y)) = o(E X^{2}), and thus

P(Var(X | Y)/(E X)^{2} > εδ^{2}) → 0.

Hence,

lim sup_{n→∞} P(Var(X | Y)/ E(X | Y)^{2} > ε) ≤ lim sup_{n→∞} P(E(X | Y) < δ E X).

The right hand side tends to 0 as δ → 0, and thus the left hand side vanishes for every ε > 0. This shows Var(X | Y)/ E(X | Y)^{2} ⟶^{p} 0. Furthermore, for every ε > 0,

lim sup_{n→∞} P(E(X | Y) = 0) ≤ lim sup_{n→∞} P(E(X | Y) < ε E X),

and thus (19) implies P(E(X | Y) = 0) → 0. The result now follows by Theorem 1. □

Note that (18) can be regarded as a condition on the variance of the absolute error X −E(X | Y) in the approximation of X by E(X | Y), while condition (8) in Theorem 1 is a condition on the (conditional) variance of the relative error X/ E(X | Y)−1. The absolute error gives less information when X varies wildly so the theorem is most useful when the variation is not too large. In fact, in all applications so far of this version of the conditional second moment method, we have Var X = O((E X)^{2}).

Example 3. Robinson and Wormald [7] considered X = the number of Hamilton cycles in a random cubic graph. In principle, they used Theorem 2 with Y = (ξ_{3}, ξ_{4}, …), where ξ_{j} is the number of cycles of length j, but they also used a truncation argument. In fact, since X = ξ_{n} (where n is the order of the graph) is one of the components of Y, E(X | Y) = X so nothing at all is gained by conditioning on Y. Instead, they condition on Y_{M} = (ξ_{3}, …, ξ_{M}) and let first n → ∞ for fixed M, and then M → ∞. We can regard their argument as a special case of the following extension of Theorem 2. We assume that Y_{M} is a variable, defined for some sequence M → ∞ and each G_{n}.

Theorem 3. Suppose that

lim_{M→∞} lim sup_{n→∞}[Var X − Var(E(X | Y_{M}))]/(E X)^{2} = 0  (21)

and

lim_{ε→0} lim sup_{M→∞} lim sup_{n→∞} P(E(X | Y_{M}) < ε E X) = 0.  (22)

Then P(X = 0) → 0.

This follows from a corresponding extension of Theorem 1.

Theorem 4. Suppose that

lim_{M→∞} lim sup_{n→∞} P(E(X | Y_{M}) = 0) = 0  (23)

and, for each ε > 0,

lim_{M→∞} lim sup_{n→∞} P(Var(X | Y_{M}) > ε E(X | Y_{M})^{2}) = 0.  (24)

Then P(X = 0) → 0.

Proof. By (10),

P(X = 0) ≤ P(Var(X | Y_{M}) > ε E(X | Y_{M})^{2}) + ε + P(E(X | Y_{M}) = 0).

The result follows from (24) and (23) by taking the lim sup as n → ∞, M → ∞ and ε → 0 (in this order). □

Proof of Theorem 3. Taking the lim sup as n → ∞, M → ∞ and δ → 0 (in this order) in (20) (with Y_{M} instead of Y), we obtain (24). Similarly, (23) follows from (22). Hence Theorem 4 applies. □

III. Another way to avoid calculating the conditional variance Var(X | Y) is to estimate the unconditional variance of the variable X/ E(X | Y). Note that this variable has mean 1 (if defined to be 1 when E(X | Y) = 0). If the variance tends to 0, (13) and (8) follow immediately and we can use Theorem 1 provided P(E(X | Y) = 0) → 0.

The drawback of this version is that we have to calculate (or at least estimate) the variance of the more complicated variable X/ E(X | Y). We may sometimes simplify the calculations by using an approximation g(Y) of E(X | Y). (The function g may also depend on the hidden parameter n.) We assume for simplicity that g(Y) > 0.

Theorem 5. Suppose that g(Y) is a positive function of Y such that

E \frac{X}{g(Y)} → 1,  (25)

Var \frac{X}{g(Y)} → 0.  (26)

Then P(X = 0) → 0.

Proof. This is immediate by Chebyshev’s inequality (2), applied to X/g(Y).

It is also easy to see that the assumptions imply the assumptions of Theorem 1. In fact, let Z = X/g(Y). Then Z → 1 in L^{2}, and thus, cf. (17), E(Var(Z | Y)) → 0 and E(Z | Y) → 1 in L^{2} (and thus in probability). Hence Var(X | Y)/ E(X | Y)^{2} = Var(Z | Y)/ E(Z | Y)^{2} ⟶^{p} 0, and P(E(X | Y) = 0) = P(E(Z | Y) = 0) → 0. □

Example 4. Janson [4] studied for example the number of spanning subtrees in G(n, p), where p may depend on n. Denote this number by X and let Y be the number of edges. Then E X = n^{n−2}p^{n−1}, which suggest an approximation of the form

c_{1}(\frac{Y}{\binom{n}{2}})^{n−1} = c_{2}(\frac{Y}{E Y} )^{n−1} = c_{2}e^{(n−1) log(Y/ E Y)}
≈ c_{2}e^{(n−1)(Y/EY −1)} = c_{3}e^{aY} ,

with a = 2p/n. It is convenient to change this a little, and we choose

g(Y) = c^{−1}(1 − a)^{−Y}

with c^{−1} = E(X(1−a)^{Y} ). Then X/g(Y) = cX(1−a)^{Y} and E(X/g(Y)) = 1. It turns out, cf. [4, (4.15) and Remark 4.1], that if lim sup p < 1 and p ≫ n^{−1/2}, then Var(X/g(Y)) → 0. Hence Theorem 5 applies; moreover, log X − log g(Y) ⟶^{p} 0, which implies that X has the same asymptotic lognormal distribution as g(Y).

Consider now the case n^{1/2}p → c > 0. Then Var X/g(Y) → α for some α > 0. However, it follows by the argument in [4, section 4] that if Y′ denotes the number of paths of length 2 in the graph, then Var(X/g(Y) − h(Y′)) → 0 for a suitable function h. Hence

Var(X/g(Y)) = Var(E(X/g(Y) | Y′)) + o(1),

and Theorem 2 applies to X/g(Y) and Y′, which again gives an asymptotic log-normal distribution of X. It follows that, in this case, X can be approximated (with small relative error) by a function of (Y, Y′). We conjecture that this is the case also when n^{1/2}p → 0 as long as n^{2/3}p → ∞ ; for smaller p we conjecture that X can be well approximated by a function of (Y, Y′, Y′′), where Y′′ is the number of subtrees of order 4 (paths of length 3 and 3-stars), as long as n^{3/4}p → ∞, and so on with more and more terms for smaller p.

The discussion above applies also to some similar variables treated in [4], for example the number of Hamilton cycles and the number of perfect matchings. Note that the result in the latter case corresponds to the hypergraph result in Example 2, and that the condition m ≫ n^{4/3} corresponds to p ≫ n^{−2/3}, which we conjectured to be the right condition for approximation by a function of Y and Y′. Note also that both Y and Y′ are functions of the sequence of vertex degrees, so the conditioning used in Example 2 is stronger than conditioning on (Y, Y′).

References

1. C. Cooper, A. Frieze, M. Molloy and B. Reed, Perfect matchings in random r-regular, s-uniform hypergraphs, Combinatorics, Probability and Computing (to appear).

2. A. Frieze and S. Janson, Perfect matchings in random s-uniform hypergraphs, preprint, Uppsala, 1994.

3. S. Janson, Random trees in a graph and trees in a random graph, Math. Proc. Camb. Phil. Soc. 100 (1986), 319–330.

4. S. Janson, The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph, Combinatorics, Probability and Computing 3 (1994) (to appear).

5. S. Janson, Random regular graphs: asymptotic distributions and contiguity, preprint, Minneapolis, 1993.

6. J. W. Moon, The second moment of the complexity of a graph, Mathematika 11 (1964), 95–98.

7. R.W. Robinson and N.C. Wormald, Almost all cubic graphs are hamiltonian, Random Struct. Alg. 3 (1992), 117–125.

8. R.W. Robinson and N.C. Wormald, Almost all regular graphs are hamiltonian, Random Struct. Alg. 5 (1994), 363–374.

9. J. Schmidt and E. Shamir, A treshold for perfect matchings in random d-pure hypergraphs, Discrete Math. 45 (1983), 287–295.

Svante Janson, Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

  E-mail address: svante.janson@math.uu.se