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 , we may want to prove that with high probability. To obtain an upper bound for , and thus a lower bound for , we first note that since takes only integer values, . Since is non-negative we can now apply Markov's inequality to obtain . Combining these we have ; the first moment method is simply the use of this inequality.
In the other direction, being "large" does not directly imply that 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 is a sequence of non-negative real-valued random variables which converge in law to a random variable . If there are finite positive constants , such that
hold for every , then it follows from the PaleyâÂÂZygmund inequality that for every and in
Consequently, the same inequality is satisfied by .
The Bernoulli bond percolation subgraph of a graph at parameter is a random subgraph obtained from by deleting every edge of with probability , independently. The infinite complete binary tree 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 with positive probability the connected component of the root in the percolation subgraph of is infinite.
Let be the percolation component of the root, and let be the set of vertices of that are at distance from the root. Let be the number of vertices in .
To prove that is infinite with positive probability, it is enough to show that . Since the events form a decreasing sequence, by continuity of probability measures this is equivalent to showing 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 (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 in ,
Since , it follows that
which is the first moment. Now comes the second moment calculation.
For each pair , in let denote the vertex in that is farthest away from the root and lies on the simple path in to each of the two vertices and , and let denote the distance from to the root. In order for , to both be in , it is necessary and sufficient for the three simple paths from to , and the root to be in . Since the number of edges contained in the union of these three paths is , we obtain
The number of pairs such that is equal to , for and equal to for . Hence, for ,
so that
which completes the proof.
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. Here, letting denote the number of all -colorings, one obtains an upper bound on the -colorability threshold, which is not tight. Considering instead the number , namely the number of nearly-balanced coloringsâÂÂi.e., those where each color class contains around verticesâÂÂone obtains an improved threshold, which is tight.