Den starka lagen om stora tal-Vad är nytt

låt X vara en realvärderad slumpmässig variabel och låt $X_1, X_2, X_3,...$ vara en oändlig sekvens av oberoende och identiskt distribuerade kopior av X. låt $\ overline{x}_n: = \frac{1}{n}(X_1 + \ldots + X_n)$ vara de empiriska medelvärdena för denna sekvens. En grundläggande sats i sannolikhetsteori är lagen om stora tal, som kommer i både en svag och en stark form:

svag lag av stort antal. Antag att det första ögonblicket ${\Bbb E} |X|$ av X är ändligt. Sedan konvergerar $\overline{x}_n$ med sannolikhet till ${\Bbb E} X$ , alltså $\lim_{n \till \infty} {\Bbb p}( |\overline{x}_n - {\Bbb E} X| \geq \varepsilon ) = 0$ för varje $\varepsilon 0$ .

stark lag av stort antal. Antag att det första ögonblicket ${\Bbb E} |X|$ av X är ändligt. Sedan $\overline{x}_n$ konvergerar nästan säkert till ${\Bbb E} X$ , alltså ${\Bbb p}( \lim_{n \till \infty} \overline{x}_n = {\Bbb E} x ) = 1$ .

(om man förstärker det första momentets antagande till det andra momentets slutlighet ${\Bbb E} / X / ^2$ , så har vi naturligtvis ett mer exakt uttalande än den (svaga) lagen om stora tal, nämligen central limit theorem, men jag kommer inte att diskutera den satsen här. Med ännu fler hypoteser på X har man på samma sätt mer exakta versioner av den starka lagen om stora tal, till exempel Chernoff-ojämlikheten, som jag återigen inte kommer att diskutera här.)

den svaga lagen är lätt att bevisa, men den starka lagen (som naturligtvis innebär den svaga lagen, genom Egoroffs sats) är mer subtil, och i själva verket visas beviset på denna lag (förutsatt att det första ögonblicket är slut) oftast bara i avancerade examenstexter. Så jag trodde att jag skulle presentera ett bevis här på båda lagarna, som fortsätter med standardteknikerna för momentmetoden och trunkering. Tyngdpunkten i denna utställning kommer att ligga på motivation och metoder snarare än korthet och styrka av resultat; det finns bevis på den starka lagen i litteraturen som har komprimerats ner till storleken på en sida eller mindre, men detta är inte mitt mål här.

— momentmetoden —

momentmetoden syftar till att kontrollera svansannolikheterna för en slumpmässig variabel (dvs. sannolikheten att den fluktuerar långt från medelvärdet) med hjälp av ögonblick, och i synnerhet nollpunkten, första eller andra ögonblicket. Anledningen till att denna metod är så effektiv är att de första ögonblicken ofta kan beräknas ganska exakt. Metoden för första ögonblicket använder vanligtvis Markovs ojämlikhet

$\displaystyle {\BBB P}( |X| \GEQ \lambda ) \leq \frac{1}{\lambda} {\Bbb E} / X|$ (1)

(vilket följer genom att ta förväntningar på den punktvisa ojämlikheten $\lambda I(|X| \geq \lambda) \leq |X|$ ), medan andra momentmetoden använder någon version av Chebyshevs ojämlikhet, såsom

$\displaystyle {\BBB P}( |X| \GEQ \lambda ) \leq \frac{1}{\lambda^2} {\Bbb E} / X|^2$ (2)

(Observera att (2) bara (1) tillämpas på den slumpmässiga variabeln ).

generellt sett använder man vanligtvis linjäritet i förväntan för att beräkna det första ögonblicket

$\displaystyle {\Bbb e} X_1 + \ldots + X_n = {\Bbb e} X_1 + \ldots + {\Bbb e} X_n$ ,

för att beräkna det andra ögonblicket måste man också förstå kovarianser (som är särskilt enkla om man antar parvis oberoende) tack vare identiteter som

$\displaystyle {\Bbb e} (X_1 + \ldots + X_n)^2 = {\Bbb e} X_1^2 + \ldots + {\Bbb e} X_n^2 + 2 \ sum_{1 \leq I j \ leq n} X_i x_j$

eller den normaliserade varianten

$\ displaystyle {\bf var} (X_1 + \ldots + X_n) = {\bf var} (X_1) + \ldots + {\bf var} (X_n)$

$\displaystyle + 2 \ sum_{1 \ leq i j \ leq n} {\bf Cov} (X_i, X_j)$ . (3)

högre moment kan i princip ge mer exakt information, men kräver ofta starkare antaganden om de objekt som studeras, såsom gemensamt oberoende.

här är en grundläggande tillämpning av första ögonblicket metoden:

Borel-Cantelli lemma. Låt $E_1, E_2, E_3, \ldots$ vara en sekvens av händelser så att $\sum_{n=1}^\infty {\Bbb p}(E_n)$ är ändlig. Då är nästan säkert bara ändligt många av händelserna $E_n$ sanna.

bevis. Låt $I (E_n)$ ange indikatorfunktionen för händelsen $E_n$ . Vår uppgift är att visa att $\sum_{n=1}^\infty I(E_n)$ är nästan säkert ändlig. Men med förväntans linjäritet är förväntan på denna slumpmässiga variabel $\sum_{n=1}^\infty {\Bbb p}(E_n)$ , vilket är ändligt av hypotesen. Genom Markovs ojämlikhet (1) drar vi slutsatsen att

$\displaystyle {\BBB p}( \sum_{n=1}^\infty I(E_n) \geq \lambda ) \leq \frac{1}{\lambda} \sum_{n=1}^\infty {\Bbb p}(E_n)$ .

låta $\lambda \ till \ infty$ vi får fordran. $\Box$

återgå till lagen om stora tal, det första ögonblicket metoden ger följande svans bunden:

Lemma 1. (Första stundens svans bunden) Om ${\Bbb E}|X|$ är ändlig, då

$\displaystyle {\Bbb p} (|\overline{x}_n|\geq \lambda) \leq\frac {{\Bbb E}|X/} {\lambda}$ .

bevis. Av triangeln ojämlikhet, $| \overline{x}_n|\leq \ overline {|X/} _n$ . Genom linjäritet av förväntan är förväntan på $\ overline {/X/} _n$ ${\Bbb E}|X|$ . Påståendet följer nu av Markovs ojämlikhet. $\ Box$

Lemma 1 är inte tillräckligt stark för att bevisa lagen om stora tal i antingen svag eller stark form – i synnerhet visar det ingen förbättring eftersom n blir stor – men det kommer att vara användbart att hantera ett av felvillkoren i dessa bevis.

vi kan få starkare gränser än Lemma 1 – i synnerhet gränser som förbättras med n – på bekostnad av starkare antaganden om X.

Lemma 2. (Second moment tail bound) om ${\Bbb E} / X / ^2$ är ändlig, då

$\displaystyle {\Bbb p} (/\overline{x}_n - {\Bbb E} (X)|\GEQ \lambda) \leq \frac{ {\Bbb E}|X - {\Bbb E}(X) / ^2 }{n \lambda^2}$ .

bevis. En standardberäkning, som utnyttjar (3) och parvis oberoende av $X_i$ , visar att variansen ${\Bbb e} |\overline{x}_n - {\Bbb E}(X)|^2$ av de empiriska medelvärdena $\overline{x}_n$ är lika med $\frac{1}{n}$ gånger variansen ${\BBB e} |x - {\BBB e}(x)|^2$ av den ursprungliga variabeln X. påståendet följer nu av chebyshevs ojämlikhet (2). $\Box$

i motsatt riktning finns zeroth moment-metoden, mer allmänt känd som union bound

$\displaystyle {\Bbb p} (E_1 \ vee \ldots \ vee E_n ) \ leq \ sum_{j=1}^n {\Bbb p} (E_j)$

eller likvärdigt (för att förklara terminologin ”zeroth moment”)

$\displaystyle {\Bbb e} (X_1 + \ldots + X_n)^0 \leq {\Bbb e} X_1^0 + \ldots + X_n^0$

för alla icke-negativa slumpmässiga variabler $X_1,\ldots, X_n \geq 0$ . Tillämpa detta på de empiriska medel, vi får nollpunkten svans uppskattning

${\Bbb p} (\overline{X}_n \ neq 0) \leq n {\Bbb P}(X \ neq 0)$ . (4)

precis som det andra momentet bundet (Lemma 2) bara är användbart när man har god kontroll på det andra momentet (eller variansen) av X, är zeroth moment tail estimate(3) bara användbart när vi har god kontroll på zeroth moment ${\Bbb E} |X|^0 = {\Bbb P} (X \neq 0)$ , dvs när X är mestadels noll.

det andra ögonblicket svansbundet (Lemma 2) ger redan den svaga lagen om stora tal i fallet när X har ändligt andra ögonblick (eller ekvivalent, ändlig varians). I allmänhet, om allt man vet om X är att det har ändligt första ögonblick, kan vi inte dra slutsatsen att X har ändligt andra ögonblick. Vi kan dock utföra en trunkering

$\displaystyle X = x_ {\leq n} + x_{N}$ (5)

n, där $x_ {\leq N}: = X I (|X|\leq N)$ och $x_{N} := X i (|X / N)$ . Den första termen $x_ {\leq n}$ har ändligt andra ögonblick; vi har helt klart

$\displaystyle {\Bbb e} / X_ {\leq n} / ^2 \leq N {\Bbb E} / X|$

och därför har vi också ändlig varians

$\displaystyle {\Bbb e} / X_ {\leq n} - {\Bbb e} X_ {\leq n} / ^2 \leq n {\Bbb E} / X /$ . (6)

den andra termen $x_{n}$ kan ha oändligt andra ögonblick, men dess första ögonblick är väl kontrollerat. Genom den monotona konvergenssatsen har vi faktiskt

$\displaystyle {\Bbb e} / X_{n} / \ till 0 \hbox{ as } N \till \ infty$ . (7)

med triangeln ojämlikhet drar vi slutsatsen att den första termen $X_ {\leq N}$ har förväntan nära ${\Bbb E} X$ :

$\displaystyle {\Bbb e} X_ {\leq n} \till {\Bbb E} (X) \hbox{ as } N \till \infty$ . (8)

dessa är alla verktyg vi behöver för att bevisa den svaga lagen i stora tal:

bevis på svag lag. Låta $\varepsilon 0$ . Det räcker att visa att när n är tillräckligt stor beroende på $\varepsilon$ , att $\ overline{x}_n = {\Bbb E} X + o (\varepsilon)$ med Sannolikhet $1-O (\varepsilon)$ .

från (7), (8) kan vi hitta ett tröskelvärde N (beroende på $\varepsilon$ ) så att ${\Bbb e} |X_{\geq N}| = o(\varepsilon^2)$ och ${\Bbb e} X_{n} = {\Bbb E} X + O(\varepsilon)$ . Nu använder vi (5) för att dela

$\displaystyle \ overline{X}_n = (\overline{X_ {\geq N}})_n +(\overline{X_{ n}}) _n$ .

från det första ögonblicket svansbundet (Lemma 1) vet vi att $(\overline{X_{\geq N}})_n = O (\varepsilon)$ med Sannolikhet $1 - O (\varepsilon)$ . Från det andra ögonblicket svansbundet (Lemma 2) och (6) vet vi att $(\overline{X_{ n}})_n = {\Bbb e} X_{n} + O(\varepsilon) = {\Bbb E} X + O(\varepsilon)$ med Sannolikhet $1-O(\varepsilon)$ om n är tillräckligt stor beroende på N och $\varepsilon$ . Påståendet följer. $\ låda$

— den starka lagen –

den starka lagen kan bevisas genom att trycka på ovanstående metoder lite längre och använda några fler knep.

det första tricket är att observera att för att bevisa den starka lagen är det tillräckligt att göra det för icke-negativa slumpmässiga variabler $x \geq 0$ . Detta följer faktiskt omedelbart av det enkla faktum att varje slumpmässig variabel X med ändligt första ögonblick kan uttryckas som skillnaden mellan två icke-negativa slumpmässiga variabler $\max(X,0), \max(-X,0)$ av ändligt första ögonblick.

när X är icke-negativ ser vi att de empiriska medelvärdena $\overline{x}_n$ inte kan minska för snabbt i n. I synnerhet observerar vi att

$\displaystyle \ overline{x}_m \ leq (1 + o (\varepsilon)) \overline{x}_n$ när $(1-\varepsilon) n \leq m \leq n$ . (9)

på grund av denna kvasimonotonicitet kan vi sparsifiera uppsättningen n för vilken vi behöver bevisa den starka lagen. Mer exakt räcker det att visa

stark lag med stort antal, reducerad version. Låt $X$ vara en icke-negativ slumpvariabel med ${\Bbb E} X \infty$ och låt $1 \leq n_1\leq n_2\leq n_3\leq\ldots$ vara en sekvens av heltal som är lakunär i den meningen att $n_{j+1}/n_j c$ för vissa $c1$ och alla tillräckligt stora j. sedan $\overline{X}_{N_j}$ konvergerar nästan säkert till ${\BBB e} x$ .

faktum är att om vi kunde bevisa den reducerade versionen, då på att tillämpa den versionen till lacunary sekvensen $n_j := \lfloor (1+\varepsilon)^j\rfloor$ och med hjälp av (9) skulle vi se att nästan säkert empiriska medel $\overline{x}_n$ inte kan avvika med mer än ett multiplikativt fel på $1 + o (\varepsilon)$ från medelvärdet ${\Bbb E} X$ . Inställning $\varepsilon: = 1/m$ för $m=1,2,3,\ldots$ (och med hjälp av det faktum att en räknbar korsning av nästan säkra händelser förblir nästan säker) får vi den fulla starka lagen.

nu när vi har sparsifierat sekvensen blir det ekonomiskt att tillämpa Borel-Cantelli lemma. Faktum är att genom många tillämpningar av den lemma ser vi att det räcker att visa att

$\displaystyle \ sum_{j=1}^ \ infty {\Bbb p} (\overline{x}_{n_j} \neq {\Bbb E} (X) + O (\varepsilon )) \infty$ (10)

för icke-negativ X av ändligt första ögonblick, någon lakunär sekvens $1 \leq n_1 \leq n_2 \leq \ldots$ och någon $\varepsilon 0$ .

vid denna tidpunkt går vi tillbaka och tillämpar de metoder som redan arbetat för att ge den svaga lagen. För att uppskatta var och en av svansannolikheterna ${\Bbb p}( \overline{x}_{n_j} \neq {\Bbb E}(X) + O(\varepsilon) )$ utför vi en trunkering (5) vid något tröskelvärde $N_j$ . Det är inte omedelbart uppenbart vilken trunkering som ska utföras, så vi antar den vanliga strategin att lämna $N_j$ ospecificerad för nu och optimera i denna parameter senare.

vi bör åtminstone välja $N_j$ tillräckligt stor så att ${\Bbb e} X_{ N_j} = {\Bbb E} X + O(\varepsilon)$ . Från det andra ögonblicket svansuppskattning (Lemma 2) drar vi slutsatsen att $(\overline{X_{ N_j}})_{n_j}$ också är lika med ${\Bbb E} X + O( \varepsilon )$ med Sannolikhet $1-O( \frac{1}{\varepsilon n_j} {\Bbb e} |X_{\leq N_j}|^2 )$ . Man kan försöka förenkla detta uttryck med (6), men det visar sig vara lite slöseri, så låt oss hålla fast vid det för tillfället. Men (6) föreslår starkt att vi vill ta $N_j$ för att vara något som $n_j$ , vilket är värt att komma ihåg i det som följer.

nu tittar vi på bidraget från $X_{\geq N_j}$ . Man kan använda första momentets svansuppskattning (Lemma 1), men det visar sig att det första ögonblicket ${\Bbb e} X_{ N_j}$ sönderfaller för långsamt i j för att vara till stor nytta (minns att vi förväntar oss att $N_j$ ska vara som lacunary sequence $n_j$ ); rotproblemet här är att förfallet (7) som kommer från monoton konvergenssatsen är ineffektivt (man kan effektivisera detta med hjälp av finita konvergensprincipen, men det visar sig att ge mycket dåliga resultat här).

men det finns ett sista kort att spela, vilket är zeroth moment method tail estimate (4). Som tidigare nämnts är denna gräns elak i allmänhet-men är mycket bra när X är mestadels noll, vilket är just situationen med $X_{N_j}$ . och i synnerhet ser vi att $(\overline{X_{N_j}}) _ {n_j}$ är noll med Sannolikhet $1-O( n_j {\Bbb P}(X N_j) )$ .

att sätta ihop allt detta ser vi att

$\displaystyle {\Bbb p} (\overline{x} _ {n_j} \neq {\Bbb E} (X) + o (\varepsilon ) ) \leq O (\frac{1} {\varepsilon n_j} {\Bbb e} / x_ {\leq N_j} / ^2) + O( n_j {\Bbb P}(X N_j)).$

Sammanfattningsvis detta i j ser vi att vi kommer att göras så snart vi räknar ut hur man väljer $N_j$ så att

$\displaystyle \ sum_{j=1}^ \ infty \ frac{1}{n_j} {\Bbb E} / x_ {\leq N_j}|^2$ (11)

och

$\displaystyle \ sum_{j=1}^ \ infty n_j {\Bbb P} (X N_j)$ (12)

båda är ändliga. (Som vanligt har vi en avvägning: att göra $N_j$ större gör (12) lättare att etablera på bekostnad av (11) och vice versa när man gör $N_j$ mindre.)

baserat på diskussionen tidigare är det naturligt att försöka ställa in $N_j := n_j$ . Lyckligtvis fungerar detta val rent; lacunary naturen av $n_j$ säkerställer (i grund och botten från den geometriska serieformeln) att vi har de punktvisa uppskattningarna

$\displaystyle \ sum_{j=1}^ \ infty \ frac{1}{n_j} / X_ {\leq n_j} / ^2 = O (X )$

och

$\displaystyle \ sum_{j = 1}^\infty n_j I (X \ geq n_j ) = O (X )$

(där den underförstådda konstanten här beror på sekvensen $n_1, n_2, \ldots$ , och i synnerhet på lacunaritetskonstanten c). Kraven (10), (11) följer sedan från en sista tillämpning av förväntans linjäritet, vilket ger den starka lagen om stort antal.

anmärkning 1. Ovanstående bevis visar faktiskt att den starka lagen om stort antal gäller även om man bara antar parvis oberoende av $X_n$ , snarare än gemensamt oberoende. $\ diamant$

Anmärkning 2. Det är viktigt att de slumpmässiga variablerna $X_1, X_2,\ldots$ ” återvinns ” från ett empiriskt medelvärde $\overline{x}_n$ till nästa, för att få den avgörande quasimonotonicity-egenskapen (9). Om vi istället tog helt oberoende medelvärden $\ overline{x}_n = \ frac{1}{n} (X_{n,1} + \ldots + x_{n,n} )$ , där $X_{I,j}$ är alla iid, bryter den starka lagen om stora tal faktiskt med bara ett första ögonblick antagande. (För ett motexempel, överväga en slumpmässig variabel X som är lika med $2^m / m^2$ med Sannolikhet $2^{-m}$ för $m=1,2,3,\ldots$ ; denna slumpmässiga variabel (knappt) har ändligt första ögonblick, men för $n \sim 2^m/m^2$ ser vi att $\overline{x}_n$ avviker med åtminstone absolut konstant från dess medelvärde med Sannolikhet $\GG 1/m^2$ . Eftersom det empiriska medlet $\ overline{x}_n$ för $n \ sim 2^m/m^2$ nu är gemensamt oberoende, är sannolikheten att en av dem avviker väsentligt nu extremt nära 1 (super-exponentiellt nära i $m$ , faktiskt), vilket leder till det totala misslyckandet av den starka lagen i denna inställning.) Naturligtvis, om man begränsar uppmärksamheten på en lakunär sekvens av n, går ovanstående bevis igenom i det oberoende fallet (eftersom Borel-Cantelli lemma är okänslig för detta oberoende). Genom att utnyttja det gemensamma självständigheten ytterligare (t.ex. genom att använda Chernoffs ojämlikhet) kan man också få den starka lagen för oberoende empiriska medel för hela sekvensen n under andra momentets gränser. $\ diamant$

Anmärkning 3. Ur interpoleringsteorins perspektiv kan man se ovanstående argument som ett interpoleringsargument och upprätta en $l^1$ uppskattning (10) genom att interpolera mellan en $L^2$ uppskattning (Lemma 2) och $L^0$ uppskattning (4). $\ diamant$

anmärkning 4. Genom att se sekvensen $X_1, X_2,\ldots$ som en stationär process, och därmed som ett speciellt fall av ett måttbevarande system kan man se den svaga och starka lagen i stora tal som speciella fall av medelvärdet respektive punktvis ergodiska satser (se Övning 9 från 254a föreläsning 8 och Sats 2 från 254a föreläsning 9). $\diamant$

den starka lagen om stora tal

Lämna ett svar Avbryt svar

Uncle Tom’ s Cabin

Falsk signatur på kontrakt: allt du behöver veta

den starka lagen om stora tal

Lämna ett svar Avbryt svar

More:

Uncle Tom’ s Cabin

Falsk signatur på kontrakt: allt du behöver veta