Second moment method

The Bernoulli bond percolation subgraph 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 T 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 p ∈ (1/2, 1] with positive probability the connected component of the root in the percolation subgraph of T is infinite.

Let K be the percolation component of the root, and let T_n be the set of vertices of T that are at distance n from the root. Let X_n be the number of vertices in T_n ∩ K. To prove that K is infinite with positive probability, it is enough to show that ${\displaystyle \limsup _{n\to \infty }1_{X_{n}>0}>0}$ with positive probability. By the reverse Fatou lemma, it suffices to show that ${\displaystyle \inf _{n\to \infty }P(X_{n}>0)>0}$. The Cauchy–Schwarz inequality gives

${\displaystyle E[X_{n}]^{2}\leq E[X_{n}^{2}]\,E\left[(1_{X_{n}>0})^{2}\right]=E[X_{n}^{2}]\,P(X_{n}>0).}$

Therefore, it is sufficient to show that

${\displaystyle \inf _{n}{\frac {E\left[X_{n}\right]^{2}}{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 T_n,

${\displaystyle P(v\in K)=p^{n}.}$

Since ${\displaystyle |T_{n}|=2^{n}}$, it follows that

${\displaystyle E[X_{n}]=2^{n}\,p^{n}}$

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

${\displaystyle E\!\left[X_{n}^{2}\right]=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}}P(v,u\in K).}$

For each pair v, u in T_n 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 2n − k(v, u), we obtain

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

The number of pairs (v, u) such that k(v, u) = s is equal to ${\displaystyle 2^{s}\,2^{n-s}\,2^{n-s-1}=2^{2n-s-1}}$, for s = 0, 1, ..., n. Hence,

${\displaystyle E\!\left[X_{n}^{2}\right]=\sum _{s=0}^{n}2^{2n-s-1}p^{2n-s}={\frac {1}{2}}\,(2p)^{n}\sum _{s=0}^{n}(2p)^{s}={\frac {1}{2}}\,(2p)^{n}\,{\frac {(2p)^{n+1}-1}{2p-1}}\leq {\frac {p}{2p-1}}\,E[X_{n}]^{2},}$

which completes the proof.

• 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 is sometimes used instead of the Cauchy–Schwarz inequality and may occasionally give more refined results.
• Under the (incorrect) assumption that the events v, u in K are always independent, one has ${\displaystyle P(v,u\in K)=P(v\in K)\,P(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

${\displaystyle X_{n}=\sum _{v\in T_{n}}1_{v\in K}.}$

In other applications, the corresponding useful random variables are integrals

${\displaystyle 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 μ × μ and calculates

${\displaystyle {\begin{aligned}E\left[X_{n}^{2}\right]&=E\left[\int \int f_{n}(x)\,f_{n}(y)\,d\mu (x)\,d\mu (y)\right]\\&=E\left[\int \int E\left[f_{n}(x)\,f_{n}(y)\right]\,d\mu (x)\,d\mu (y)\right],\end{aligned}}}$

where the last step is typically justified using Fubini's theorem.