# Second moment method

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Second_moment_method
> Markdown URL: https://mediated.wiki/source/Second_moment_method.md
> Source: https://en.wikipedia.org/wiki/Second_moment_method
> Source revision: 1344453056
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In mathematics, the **second moment method** is a technique used in [probability theory](/source/Probability_theory) and [analysis](/source/Analysis) to show that a [random variable](/source/Random_variable) has positive probability of being positive. More generally, the "moment method" consists of bounding the probability that a random variable fluctuates far from its mean, by using its moments.[1]

The method is often quantitative, in that one can often deduce a lower bound on the probability that the random variable is larger than some constant times its expectation. The method involves comparing the second [moment](/source/Moment_(mathematics)) of random variables to the square of the first moment.

## First moment method

The first moment method is a simple application of [Markov's inequality](/source/Markov's_inequality) for integer-valued variables. For a **non-negative**, **integer-valued** random variable *X*, we may want to prove that *X* = 0 with high probability. To obtain an upper bound for Pr(*X* > 0), and thus a lower bound for Pr(*X* = 0), we first note that since *X* takes only [integer](/source/Integer) values, Pr(*X* > 0) = Pr(*X* ≥ 1). Since *X* is non-negative we can now apply Markov's inequality to obtain Pr(*X* ≥ 1) ≤ E[*X*]. Combining these we have Pr(*X* > 0) ≤ E[*X*]; the first moment method is simply the use of this inequality.

## Second moment method

In the other direction, E[*X*] being "large" does not directly imply that Pr(*X* = 0) is small. However, we can often use the second moment to derive such a conclusion, using the [Cauchy–Schwarz inequality](/source/Cauchy%E2%80%93Schwarz_inequality).

The method can also be used on distributional limits of random variables. Furthermore, the estimate of the previous theorem can be refined by means of the so-called [Paley–Zygmund inequality](/source/Paley%E2%80%93Zygmund_inequality). Suppose that *Xn* is a sequence of non-negative real-valued random variables which [converge in law](/source/Converge_in_law) to a random variable *X*. If there are finite positive constants *c*1, *c*2 such that

\begin{align}
\operatorname{E} \left [X_n^2 \right ] &\le c_1 \operatorname{E}[X_n]^2 \\
\operatorname{E} \left [X_n \right ] &\ge c_2
\end{align}

hold for every n, then it follows from the [Paley–Zygmund inequality](/source/Paley%E2%80%93Zygmund_inequality) that for every n and θ in

\Pr (X_n \geq c_2 \theta) \geq \frac{(1-\theta)^2}{c_1}.

Consequently, the same inequality is satisfied by X.

## Example application of method

### Setup of problem

The [Bernoulli bond percolation](/source/Bernoulli_bond_percolation) [subgraph](/source/Glossary_of_graph_theory#Subgraphs) of a graph G at parameter p is a random subgraph obtained from G by deleting every edge of G with probability 1−*p*, independently. The [infinite complete binary tree](/source/Binary_tree) T is an infinite [tree](/source/Tree_(graph_theory)) where one vertex (called the root) has two neighbors and every other vertex has three neighbors. The second moment method can be used to show that at every parameter *p* ∈ with positive probability the connected component of the root in the percolation subgraph of T is infinite.

### Application of method

Let K be the percolation component of the root, and let *Tn* be the set of vertices of T that are at distance n from the root. Let *Xn* be the number of vertices in *Tn* ∩ *K*.

To prove that K is infinite with positive probability, it is enough to show that \Pr(X_n>0\ \ \forall n)>0. Since the events \{X_n>0\} form a decreasing sequence, by continuity of probability measures this is equivalent to showing that \inf_{n}\Pr(X_n>0)>0.

The [Cauchy–Schwarz inequality](/source/Cauchy%E2%80%93Schwarz_inequality) gives

\operatorname{E}[X_n]^2\le \operatorname{E}[X_n^2] \, \operatorname{E}\left [(1_{X_n>0})^2\right ] = \operatorname{E}[X_n^2]\,\Pr(X_n>0).

Therefore, it is sufficient to show that

\inf_n \frac{\operatorname{E} \left[ X_n \right ]^2}{\operatorname{E} \left[ X_n^2 \right ]}>0\,,

that is, that the second moment is bounded from above by a constant times the first moment squared (and both are nonzero). In many applications of the second moment method, one is not able to calculate the moments precisely, but can nevertheless establish this inequality.

In this particular application, these moments can be calculated. For every specific v in *Tn*,

\Pr(v\in K) = p^n.

Since |T_n| = 2^n, it follows that

\operatorname{E}[X_n] = 2^n\,p^n

which is the first moment. Now comes the second moment calculation.

\operatorname{E}\!\left[X_n^2 \right ] = \operatorname{E}\!\left[\sum_{v\in T_n} \sum_{u\in T_n}1_{v\in K}\,1_{u\in K}\right] = \sum_{v\in T_n} \sum_{u\in T_n} \Pr(v,u\in K).

For each pair v, u in *Tn* let *w*(*v*, *u*) denote the vertex in *T* that is farthest away from the root and lies on the simple path in *T* to each of the two vertices v and u, and let *k*(*v*, *u*) denote the distance from *w* to the root. In order for v, u to both be in *K*, it is necessary and sufficient for the three simple paths from *w*(*v*, *u*) to v, u and the root to be in *K*. Since the number of edges contained in the union of these three paths is 2*n* − *k*(*v*, *u*), we obtain

\Pr(v,u\in K) = p^{2n-k(v,u)}.

The number of pairs (*v*, *u*) such that *k*(*v*, *u*) = *s* is equal to 2^s\,2^{n-s}\,2^{n-s-1} = 2^{2n-s-1}, for s=0,1,\dots,n-1 and equal to 2^n for s=n. Hence, for p>\frac 1 2,

\operatorname{E}[ X_n^2 ]= (2p)^n + \sum_{s=0}^{n-1} 2^{2n-s-1} p^{2n-s} = \frac{(2p)^{n+1}-2(2p)^n+(2p)^{2n+1}}{4p-2} ,

so that

\frac{(\operatorname{E} [X_n])^2}{\operatorname{E} [X_n^2]} = \frac{4p-2}{(2p)^{1-n}-2(2p)^{-n}+2p} \to 2 - \frac{1}{p} > 0,

which completes the proof.

### Choice of random variable

The choice of the random variable to which the moment method is applied often makes a difference. One example arises in the context of [graph coloring](/source/Graph_coloring). Here, letting Z denote the number of all q-colorings, one obtains an upper bound on the q-colorability threshold, which is not tight. Considering instead the number Zbal, namely the number of nearly-balanced colorings—i.e., those where each color class contains around n/q vertices—one obtains an improved threshold, which is tight.

### Discussion

- The choice of the random variables *X**n* was rather natural in this setup. In some more difficult applications of the method, some ingenuity might be required in order to choose the random variables *X**n* for which the argument can be carried through.
- The [Paley–Zygmund inequality](/source/Paley%E2%80%93Zygmund_inequality) is sometimes used instead of the [Cauchy–Schwarz inequality](/source/Cauchy%E2%80%93Schwarz_inequality) and may occasionally give more refined results.
- Under the (incorrect) assumption that the events v, u in K are always independent, one has \Pr(v,u\in K) = \Pr(v\in K) \, \Pr(u\in K), and the second moment is equal to the first moment squared. The second moment method typically works in situations in which the corresponding events or random variables are “nearly independent".
- In this application, the random variables *X**n* are given as sums

X_n = \sum_{v \in T_n} 1_{v\in K}.

In other applications, the corresponding useful random variables are integrals

X_n = \int f_n(t)\,d\mu(t),

where the functions *f**n* are random. In such a situation, one considers the [product measure](/source/Product_measure) *μ* × *μ* and calculates

\begin{align}
\operatorname{E} \left[X_n^2 \right ] & = \operatorname{E}\left[\iint f_n(x)\,f_n(y)\,d\mu(x)\,d\mu(y)\right ] \\
& = \operatorname{E}\left[ \iint \operatorname{E}\left[f_n(x)\,f_n(y)\right]\,d\mu(x)\,d\mu(y)\right ],
\end{align}

where the last step is typically justified using [Fubini's theorem](/source/Fubini's_theorem).

## References

1. Terence Tao (2008-06-18). ["The strong law of large numbers"](http://terrytao.wordpress.com/2008/06/18/the-strong-law-of-large-numbers/). *What’s new?*. Retrieved 2009-02-10.

- Burdzy, Krzysztof; Adelman, Omer; Pemantle, Robin (1998), "Sets avoided by Brownian motion", *Annals of Probability*. **26** (2): 429–464, [arXiv:math/9701225](https://arxiv.org/abs/math/9701225). [doi:10.1214/aop/1022855639](https://doi.org/10.1214/aop/1022855639). [hdl:1773/2194](https://hdl.handle.net/1773/2194). [S2CID 7338064](https://api.semanticscholar.org/CorpusID:7338064)
- Lyons, Russell (1992), "Random walk, capacity, and percolation on trees", *Annals of Probability*. **20** (4): 2043–2088, [doi:10.1214/aop/1176989540](https://doi.org/10.1214/aop/1176989540)
- Lyons, Russell & Peres, Yuval, ["Probability on trees and networks"](https://web.archive.org/web/20060502093416/http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html), archived from [the original](http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html) on 2006-05-02, retrieved 2008-07-13

---
Adapted from the Wikipedia article [Second moment method](https://en.wikipedia.org/wiki/Second_moment_method) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Second_moment_method?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.