Andra momentmetod

Inom matematik är den andra momentmetoden en teknik som används inom sannolikhetsteori och analys för att visa att en slumpvariabel har positiv sannolikhet att vara positiv. Mer generellt består "momentmetoden" av att begränsa sannolikheten för att en slumpvariabel fluktuerar långt från sitt medelvärde, genom att använda dess moment.

Metoden är ofta kvantitativ, i det att man ofta kan härleda en nedre gräns för sannolikheten att den stokastiska variabeln är större än någon konstant gånger sin förväntan. Metoden går ut på att jämföra det andra momentet av slumpvariabler med kvadraten på det första momentet.

Första ögonblickets metod

Första momentmetoden är en enkel tillämpning av Markovs olikhet för heltalsvärderade variabler. För en icke-negativ slumpvariabel X med heltalsvärde kanske vi vill bevisa att X = 0 med hög sannolikhet . För att få en övre gräns för P( X > 0), och därmed en nedre gräns för P( X = 0), noterar vi först att eftersom X endast tar heltalsvärden, P( X > 0) = P( X ≥ 1) . Eftersom X är icke-negativ kan vi nu tillämpa Markovs olikhet för att erhålla P( X ≥ 1) ≤ E[ X ]. Genom att kombinera dessa har vi P( X > 0) ≤ E[ X ]; den första ögonblicksmetoden är helt enkelt användningen av denna ojämlikhet.

Andra momentmetod

I den andra riktningen innebär att E[ X ] är "stor" inte direkt att P( X = 0) är liten. Men vi kan ofta använda det andra ögonblicket för att dra en sådan slutsats genom att använda Cauchy–Schwarz-ojämlikhet .

Sats : Om X ≥ 0 är en stokastisk variabel med ändlig varians, då

$\operatörsnamn {P} (X>0)\geq {\frac {(\operatörsnamn {E} [X])^{2}}{\operatörsnamn {E} [X^{2}]}}.$

Bevis : Genom att använda Cauchy–Schwarz-ojämlikheten har vi

$\operatörsnamn {E} [X]=\operatörsnamn {E} [X\,\mathbf {1} _{\{X>0\}}]\leq \operatörsnamn {E} [X^{2} ]^{1/2}\operatörsnamn {P} (X>0)^{1/2}.$

Löser man $\operatorname {P} (X>0)$ , den önskade olikheten följer sedan. ∎

Metoden kan även användas på fördelningsgränser för stokastiska variabler. Dessutom kan uppskattningen av den tidigare satsen förfinas med hjälp av den så kallade Paley-Zygmund-olikheten . Antag att X _n är en sekvens av icke-negativa reella slumpvariabler som konvergerar i lag till en slumpvariabel X . Om det finns ändliga positiva konstanter c ₁ , c ₂ så att

$\operatörsnamn {E} \left[X_{n}^{2}\right]\leq c_{1}\operatörsnamn {E} [X_{n}]^{2}$

$\operatörsnamn {E} \left[X_{n}\right]\geq c_{2}$

håll för varje n , då följer det av Paley-Zygmund-olikheten att för varje n och θ i (0, 1)

$\operatorname {P} (X_{n}\geq c_{2}\theta )\geq {\frac {(1-\theta )^{2}}{c_{1}}}.$

Följaktligen uppfylls samma olikhet av X .

Exempel på tillämpning av metod

Installation av problem

Bernoulli-bindningsperkolationssubgrafen i en graf G vid parameter p är en slumpmässig subgraf som erhålls från G genom att radera varje kant av G med sannolikhet 1− p , oberoende. Det oändliga kompletta binära trädet T är ett oändligt träd där en vertex (kallad rot) har två grannar och varannan vertex har tre grannar. Den andra momentmetoden kan användas för att visa att vid varje parameter p ∈ (1/2, 1] med positiv sannolikhet är den anslutna komponenten av roten i perkolationssubgrafen av T oändlig.

Tillämpning av metod

Låt K vara perkolationskomponenten för roten, och låt T _n vara uppsättningen av hörn av T som är på avstånd n från roten. Låt X _n vara antalet hörn i T _n ∩ K . För att bevisa att K är oändlig med positiv sannolikhet räcker det att visa att $\limsup _{n\to \infty }1_{X_{n}>0}>0$ med positiv sannolikhet. Med det omvända Fatou-lemmat räcker det att visa att $\inf _{n\to \infty }P(X_{n}>0)>0$ . Cauchy –Schwarz ojämlikheten ger

$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).$

Därför är det tillräckligt att visa det

$\inf _{n}{\frac {E\left[X_{n}\right]^{2}}{E\left[ X_{n}^{2}\right]}}>0\,,$

det vill säga att det andra momentet begränsas uppifrån av en konstant gånger det första momentet i kvadrat (och båda är icke-noll). I många tillämpningar av den andra momentmetoden kan man inte beräkna momenten exakt, men kan ändå fastställa denna ojämlikhet.

I denna speciella applikation kan dessa moment beräknas. För varje specifik v i T _n ,

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

Sedan $|T_{n}|=2^{n}$ , det följer att

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

vilket är det första ögonblicket. Nu kommer andra momentberäkningen.

$E\!\left[X_{n}^{2}\right]=E\!\left[\summa _{v\in T_{n}}\summa _{u\in T_{n} }1_{v\in K}\,1_{u\in K}\right]=\summa _{v\in T_{n}}\summa _{u\in T_{n}}P(v,u \bläck).$

För varje par v , u i T _n låt w(v, u) beteckna toppunkten i T som är längst bort från roten och ligger på den enkla vägen i T till var och en av de två hörnen v och u , och låt k( v, u) betecknar avståndet från w till roten. För att v , u båda ska vara i K är det nödvändigt och tillräckligt att de tre enkla vägarna från w(v, u) till v , u och roten är i K . Eftersom antalet kanter som ingår i föreningen av dessa tre banor är 2 n − k(v, u) får vi

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

Antalet par (v, u) så att k(v, u) = s är lika med ${\displaystyle 2^{s} \,2^{ns}\,2^{ns-1}=2^{2n-s-1}} ,$ för s = 0, 1, ..., n . Därav,

$E\!\left[X_{n}^{2}\right]=\summa _{s =0}^{n}2^{2n-s-1}p^{2n-s}={\frac {1}{2}}\,(2p)^{n}\summa _{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},$

vilket kompletterar beviset.

Diskussion

• Valet av de slumpmässiga variablerna X _n var ganska naturligt i denna uppsättning. I vissa svårare _{tillämpningar} av metoden kan det krävas en del uppfinningsrikedom för att välja de slumpvariabler Xn för vilka argumentet kan genomföras.
• Paley -Zygmund-ojämlikheten används ibland istället för Cauchy-Schwarz-ojämlikheten och kan ibland ge mer raffinerade resultat.
• Under det (felaktiga) antagandet att händelserna v , u i K alltid är oberoende, har man ${\displaystyle P(v,u\ i K)=P(v\in K)\,P(u\in K)} ,$ och det andra momentet är lika med det första momentet i kvadrat. Den andra momentmetoden fungerar vanligtvis i situationer där motsvarande händelser eller slumpvariabler är "nästan oberoende".
• ges de slumpmässiga variablerna X _{n som summor}

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

I andra applikationer är motsvarande användbara slumpvariabler integraler

$X_{n}=\int f_{n}(t)\,d\mu (t),$

där funktionerna f _n är slumpmässiga. I en sådan situation betraktar man produktmåttet μ × μ och beräknar

${\begin{aligned}E\left[X_{n}^{2}\right ]&=E\vänster[\int \int f_{n}(x)\,f_{n}(y)\,d\mu (x)\,d\mu (y)\höger]\\&= E\vänster[\int \int E\vänster[f_{n}(x)\,f_{n}(y)\höger]\,d\mu (x)\,d\mu (y)\höger] ,\end{aligned}}$

där det sista steget vanligtvis motiveras med Fubinis sats .

• Burdzy, Krzysztof; Adelman, Omer; Pemantle, Robin (1998), "Set avoided by Brownian motion", Annals of Probability , 26 ( 2): 429–464, arXiv : math/9701225 , doi : 10.1214/aop/1022855639 , hdl 73/3219, 4219 , 73/3219 , 4219  
• Lyons, Russell (1992), "Random walk, capacity, and percolation on trees", Annals of Probability , 20 (4): 2043–2088, doi : 10.1214/aop/1176989540
• Lyons, Russell; Peres, Yuval, Sannolikhet på träd och nätverk