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 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 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.
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
E [ X n 2 ] ≤ c 1 E [ X n ] 2 E [ X n ] ≥ c 2 {\displaystyle {\begin{aligned}\operatorname {E} \left[X_{n}^{2}\right]&\leq c_{1}\operatorname {E} [X_{n}]^{2}\\\operatorname {E} \left[X_{n}\right]&\geq c_{2}\end{aligned}}}
hold for every n, then it follows from the Paley–Zygmund inequality that for every n and θ in (0, 1)
Pr ( X n ≥ c 2 θ ) ≥ ( 1 − θ ) 2 c 1 . {\displaystyle \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 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.
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 ∀ n ) > 0 {\displaystyle \Pr(X_{n}>0\ \ \forall n)>0} . Since the events { X n > 0 } {\displaystyle \{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 {\displaystyle \inf _{n}\Pr(X_{n}>0)>0} . The Cauchy–Schwarz inequality gives
… excerpt ends here. Continue reading the full article.
