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.
The first moment method is a simple application of 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 P, and thus a lower bound for P, we first note that since X takes only integer values, P = P. Since X is non-negative we can now apply Markov's inequality to obtain P ≤ E. Combining these we have P ≤ E; the first moment method is simply the use of this inequality.
In the other direction, E being "large" does not directly imply that P is small. However, we can often use the second moment to derive such a conclusion, using Cauchy–Schwarz inequality. Theorem: If X ≥ 0 is a random variable with finite variance, then Proof: Using the Cauchy–Schwarz inequality, we have Solving for, the desired inequality then follows. ∎ 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 Xn is a sequence of non-negative real-valued random variables which converge in law to a random variable X. If there are finite positive constants c1, c2 such that hold for every n, then it follows from the Paley–Zygmund inequality that for every n and θ in Consequently, the same inequality is satisfied by X.
Example application of method
Setup of problem
The Bernoulli bond percolationsubgraph 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 treeT is an infinite tree where one vertex 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.
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 with positive probability. By the reverse Fatou lemma, it suffices to show that. The Cauchy–Schwarz inequality gives Therefore, it is sufficient to show that that is, that the second moment is bounded from above by a constant times the first moment squared. 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, Since, it follows that which is the first moment. Now comes the second moment calculation. For each pair v, u in Tn let w 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 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 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, we obtain The number of pairs such that k = s is equal to, for s = 0, 1,..., n. Hence, which completes the proof.
Discussion
The choice of the random variables Xn 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 Xn 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 assumption that the events v, u in K are always independent, one has, 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 Xn are given as sums
