Second moment method

In mathematics, the second moment method is a technique used in probability theory and analysis to show that a 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.

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 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 for integer-valued variables. For a non-negative, integer-valued random variable Template:Math, we may want to prove that Template:Math with high probability. To obtain an upper bound for Template:Math, and thus a lower bound for Template:Math, we first note that since Template:Math takes only integer values, Template:Math. Since Template:Math is non-negative we can now apply Markov's inequality to obtain Template:Math. Combining these we have Template:Math; the first moment method is simply the use of this inequality.

Second moment method

In the other direction, Template:Math being "large" does not directly imply that Template:Math is small. However, we can often use the second moment to derive such a conclusion, using the Cauchy–Schwarz 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. Suppose that Template:Math is a sequence of non-negative real-valued random variables which converge in law to a random variable Template:Math. If there are finite positive constants Template:Math, Template:Math such that $$\begin{array}{cc}\mathrm{E}\left[X_n^2\right]& \le c_1\mathrm{E}[X_n{]}^2\\ \mathrm{E}\left[X_n\right]& \ge c_2\end{array}$$

hold for every Template:Mvar, then it follows from the Paley–Zygmund inequality that for every Template:Mvar and Template:Mvar in Template:Open-open $$\mathrm{Pr}(X_n\ge c_2\theta )\ge \frac{(1-\theta {)}^2}{c_1}.$$

Consequently, the same inequality is satisfied by Template:Mvar.

Example application of method

Setup of problem

The Bernoulli bond percolation subgraph of a graph Template:Mvar at parameter Template:Mvar is a random subgraph obtained from Template:Mvar by deleting every edge of Template:Mvar with probability Template:Math, independently. The infinite complete binary tree Template:Mvar is an infinite tree 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 Template:Math with positive probability the connected component of the root in the percolation subgraph of Template:Mvar is infinite.

Application of method

Let Template:Mvar be the percolation component of the root, and let Template:Math be the set of vertices of Template:Mvar that are at distance Template:Mvar from the root. Let Template:Math be the number of vertices in Template:Math.

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

The Cauchy–Schwarz inequality gives $$\mathrm{E}[X_n{]}^2\le \mathrm{E}[X_n^2]\mathrm{E}[(1_{X_n>0}{)}^2]=\mathrm{E}[X_n^2]\mathrm{Pr}(X_n>0).$$ Therefore, it is sufficient to show that $$\underset{n}{\inf }\frac{\mathrm{E}{\left[X_n\right]}^2}{\mathrm{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 Template:Mvar in Template:Math, $$\mathrm{Pr}(v\in K)=p^n.$$ Since $|T_n|=2^n$, it follows that $$\mathrm{E}[X_n]=2^n{p}^n$$ which is the first moment. Now comes the second moment calculation. $$\mathrm{E}\left[X_n^2\right]=\mathrm{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}\mathrm{Pr}(v,u\in K).$$ For each pair Template:Mvar, Template:Mvar in Template:Math let Template:Math denote the vertex in Template:Math that is farthest away from the root and lies on the simple path in Template:Math to each of the two vertices Template:Mvar and Template:Mvar, and let Template:Math denote the distance from Template:Math to the root. In order for Template:Mvar, Template:Mvar to both be in Template:Math, it is necessary and sufficient for the three simple paths from Template:Math to Template:Mvar, Template:Mvar and the root to be in Template:Math. Since the number of edges contained in the union of these three paths is Template:Math, we obtain $$\mathrm{Pr}(v,u\in K)=p^{2n-k(v,u)}.$$ The number of pairs Template:Math such that Template:Math 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}$, $$\mathrm{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{(\mathrm{E}[X_n]{)}^2}{\mathrm{E}[X_n^2]}=\frac{4p-2}{(2p{)}^{1-n}-2(2p{)}^{-n}+2p}\to 2-\frac{1}{p}>0,$$ which completes the proof.

Discussion

• The choice of the random variables Template:Math 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 Template:Math for which the argument can be carried through.
• The Paley–Zygmund inequality is sometimes used instead of the Cauchy–Schwarz inequality and may occasionally give more refined results.
• Under the (incorrect) assumption that the events Template:Mvar, Template:Mvar in Template:Mvar are always independent, one has $\mathrm{Pr}(v,u\in K)=\mathrm{Pr}(v\in K)\mathrm{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 Template:Math 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 Template:Math are random. In such a situation, one considers the product measure Template:Math and calculates $$\begin{array}{cc}\mathrm{E}\left[X_n^2\right]& =\mathrm{E}[\iint f_n(x)f_n(y)d\mu (x)d\mu (y)]\\ & =\mathrm{E}[\iint \mathrm{E}[f_n(x)f_n(y)]d\mu (x)d\mu (y)],\end{array}$$ where the last step is typically justified using Fubini's theorem.

References

• Template:Citation
• Template:Citation
• Template:Citation