Second moment method

Second moment method

The second moment method is a technique used in probability theory and analysis to show that a random variable has positive probability to be positive. The method is often quantitative, in that one can often deducea 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.

Example application of method

etup 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 pin (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 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_ncap K. To prove that K is infinite with positive probability, it is enough to show that limsup_{n oinfty}1_{X_n>0}>0 with positive probability. By the reverse Fatou lemma, it suffices to show that inf_{n oinfty}P(X_n>0)>0. The Cauchy-Schwarz inequality gives:E(X_n)^2le E(X_n^2) , Eigl((1_{X_n>0})^2igr)=E(X_n^2),P(X_n>0).Therefore, it is sufficient to show that:inf_n frac{E(X_n)^2}{E(X_n^2)}>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 vin T_n,:P(vin K)=p^n.Since |T_n|=2^n, it follows that:E(X_n)=2^n,p^nwhich is the first moment.Now comes the second moment calculation. :E(X_n^2)=EBigl(sum_{vin T_n} sum_{uin T_n}1_{vin K},1_{uin K}Bigr)=sum_{vin T_n}sum_{uin T_n} P(v,uin K).For each pair v,uin 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 2,n-k(v,u), we obtain:P(v,uin K)= p^{2n-k(v,u)}.

The number of pairs (v,u) such that k(v,u)=s is equal to 2^s,2^{n-s},2^{n-s-1}=2^{2n-s-1}, for s=0,1,dots,n. Hence,:E(X_n^2)=sum_{s=0}^n 2^{2n-s-1} p^{2n-s}=frac 12,(2p)^{n}sum_{s=0}^n(2p)^{s}=frac12,(2p)^n,frac{(2p)^{n+1}-1}{2p-1}le frac p{2p-1} ,E(X_n)^2, which completes the proof.

Discussion

*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 Cauchy-Schwarz and may occationally give more refined results.
*Under the (incorrect) assumption that the events vin K and uin K are always independent, one has P(v,uin K)=P(vin K),P(uin 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 X_n=sum_{vin T_n}1_{vin K}. In other applications, the corresponding useful random variables are integrals X_n=int f_n(t),dmu(t), where the functions f_n are random. In such a situation, one considers the product measure mu imes mu and calculates::E(X_n^2)=EBigl(intint f_n(x),f_n(y),dmu(x),dmu(y)Bigr)=EBigl(intint Eigl(f_n(x),f_n(y)igr),dmu(x),dmu(y)Bigr),:where the last step is typically justified using Fubini's theorem.

References

*Citation | last1=Burdzy | first1=Krzysztof | last2=Adelman | first2=Omer | last3=Pemantle | first3=Robin | title=Sets avoided by Brownian motion | url=http://hdl.handle.net/1773/2194 | year=1998 | journal=Annals of Probability | volume=26 | issue=2 | pages=429–464
*Citation | last1=Lyons | first1=Russell | title=Random walk, capacity, and percolation on trees | year=1992 | journal=Annals of Probability | volume=20 | pages=2043–2088
*Citation | last1=Lyons | first1=Russell | last2=Peres | first2=Yuval | title=Probability on trees and networks | url=http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Second moment of area — The second moment of area, also known as the area moment of inertia or second moment of inertia, is a property of a shape that is used to predict its resistance to bending and deflection which are directly proportional. This is why beams with… …   Wikipedia

  • Moment (mathematics) — Second moment redirects here. For the technique in probability theory, see Second moment method. See also: Moment (physics) Increasing each of the first four moments in turn while keeping the others constant, for a discrete uniform distribution… …   Wikipedia

  • Method of moments — may refer to: Method of moments (statistics), a method of parameter estimation in statistics Method of moments (probability theory), a way of proving convergence in distribution in probability theory Second moment method, a technique used in… …   Wikipedia

  • Method of moments (statistics) — See method of moments (probability theory) for an account of a technique for proving convergence in distribution. In statistics, the method of moments is a method of estimation of population parameters such as mean, variance, median, etc. (which… …   Wikipedia

  • Moment of inertia — This article is about the moment of inertia of a rotating object, also termed the mass moment of inertia. For the moment of inertia dealing with the bending of a beam, also termed the area moment of inertia, see second moment of area. In… …   Wikipedia

  • moment — [ mɔmɑ̃ ] n. m. • 1119; lat. momentum, contract. de movimentum « mouvement » I ♦ 1 ♦ Espace de temps limité (relativement à une durée totale) considéré le plus souvent par rapport aux faits qui le caractérisent. ⇒ 2. instant, intervalle; heure,… …   Encyclopédie Universelle

  • Second Intifada — Part of the Israeli–Palestinian conflict and Arab–Israeli conflict Clockwise from above: A masked P …   Wikipedia

  • Second sight — is a form of extra sensory perception whereby a person perceives information, in the form of vision, about future events before they happen. Foresight expresses the meaning of second sight, which perhaps was originally so called because normal… …   Wikipedia

  • Method Man — aux Eurockéennes 2007. Surnom Mr Meth, Johnny Blaze, Ticallion Stallion, Tical, Methtical (Meth tical), MZA, Iron Lung, Hot Ni …   Wikipédia en Français

  • Method man — Method Man aux Eurockéennes 2007. Alias Mr Meth, Johnny Blaze, Ticallion Stallion, Tical, Methtical (Meth tical) …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”