Azumas ojämlikhet

I sannolikhetsteorin ger Azuma–Hoeffding-ojämlikheten (uppkallad efter Kazuoki Azuma och Wassily Hoeffding) ett koncentrationsresultat för värdena martingaler som har begränsat skillnader .

Antag att är en martingal (eller supermartingal ) och

nästan säkert . Sedan för alla positiva heltal N och alla positiva reella ,

Och symmetriskt (när Xk är en submartingal) :

Om X är en martingal kan man få en tvåsidig gräns genom att använda båda olikheterna ovan och tillämpa unionsgränsen :

Bevis

Beviset delar liknande idé om beviset för den allmänna formen av Azumas ojämlikhet som anges nedan. Egentligen kan detta ses som en direkt följd av den allmänna formen av Azumas ojämlikhet.

En allmän form av Azumas ojämlikhet

Begränsning av vaniljen Azumas ojämlikhet

Observera att vanilj Azumas ojämlikhet kräver symmetriska gränser på martingalinkrement, dvs . Så, om känd gräns är asymmetrisk, t.ex. , för att använda Azumas ojämlikhet måste man välja vilket kan vara ett slöseri med information om avgränsningen av . Detta problem kan dock lösas och man kan få en snävare sannolikhet bunden med följande allmänna form av Azumas ojämlikhet.

Påstående

Låt vara en martingal (eller supermartingal) med avseende på filtrering . Antag att det finns förutsägbara processer och med avseende på , dvs för alla , är - mätbar , och konstanter så att

nästan säkert. Sedan för alla ,

Eftersom en submartingal är en supermartingal med omvända tecken, har vi om istället är en martingal ( eller submartingale),

Om är en martingal, eftersom den är både en supermartingal och submartingal, genom att tillämpa unionsbunden till de två ojämlikheterna ovan kan vi få den tvåsidiga gränsen:

Bevis

Vi kommer bara att bevisa supermartingale-fallet eftersom resten är självklara. Genom Doob-sönderdelning skulle vi kunna dekomponera supermartingale som där är en martingal och en icke-ökande förutsägbar sekvens (Observera att om i sig är en martingal, då ). Från har vi

Genom att tillämpa Chernoff bundet till , har vi för ,

För den inre förväntade termen, eftersom (i) eftersom är en martingal; ( ) ; (iii) och är båda - mätbar som är en förutsägbar process; och (iv) genom att tillämpa Hoeffdings lemma , har vi

Upprepa detta steg kan man få

Observera att minimum uppnås vid , så vi har

Slutligen, eftersom och som är icke-ökande, så händelsen antyder och därför

Anmärkning

Observera att genom att sätta kan vi få vanilj Azumas ojämlikhet.

Observera att för antingen submartingale eller supermartingale, gäller bara en sida av Azumas ojämlikhet. Vi kan inte säga så mycket om hur snabbt en submartingal med avgränsade steg stiger (eller en supermartingal faller).

Denna allmänna form av Azumas ojämlikhet tillämpad på Doob-martingalen ger McDiarmids ojämlikhet, vilket är vanligt i analysen av randomiserade algoritmer .


Enkelt exempel på Azumas ojämlikhet för myntvändningar

Låt F i vara en sekvens av oberoende och identiskt fördelade slumpmässiga myntvändningar (dvs låt F i vara lika sannolikt att vara −1 eller 1 oberoende av de andra värdena på F i ). Att definiera ger en martingal med | X k X k −1 | ≤ 1, vilket gör att vi kan tillämpa Azumas ojämlikhet. Närmare bestämt får vi

Till exempel, om vi sätter t proportionellt mot n , då säger detta oss att även om det maximalt möjliga värdet av X n skalas linjärt med n , så minskar sannolikheten att summan skalas linjärt med n exponentiellt snabbt med n .

Om vi ​​sätter får vi:

vilket innebär att sannolikheten att avvika mer än närmar sig 0 när n går till oändlighet.

Anmärkning

En liknande ojämlikhet bevisades under svagare antaganden av Sergej Bernstein 1937.

Hoeffding bevisade detta resultat för oberoende variabler snarare än martingalskillnader, och observerade också att små modifieringar av hans argument etablerar resultatet för martingalskillnader (se sidan 9 i hans artikel från 1963).

Se även

Anteckningar

  • Alon, N.; Spencer, J. (1992). Den probabilistiska metoden . New York: Wiley.
  •   Azuma, K. (1967). "Viktade summor av vissa beroende slumpmässiga variabler" (PDF) . Tôhoku Mathematical Journal . 19 (3): 357–367. doi : 10.2748/tmj/1178243286 . MR 0221571 .
  • Bernstein, Sergei N. (1937). На определенных модификациях неравенства Чебишева [Om vissa modifikationer av Chebyshevs ojämlikhet]. Doklady Akademii Nauk SSSR (på ryska). 17 (6): 275–277. (bd 4, punkt 22 i de samlade verken)
  •   McDiarmid, C. (1989). "Om metoden för avgränsade skillnader". Undersökningar i kombinatorik . London Math. Soc. Föreläsningsanteckningar 141. Cambridge: Cambridge Univ. Tryck. s. 148–188. MR 1036755 .
  •    Hoeffding, W. (1963). "Sannolikhetsolikheter för summor av gränsade stokastiska variabler" . Journal of the American Statistical Association . 58 (301): 13–30. doi : 10.2307/2282952 . JSTOR 2282952 . MR 0144363 .
  •    Godbole, AP; Hitczenko, P. (1998). Bortom metoden för avgränsade skillnader . DIMACS-serien i diskret matematik och teoretisk datavetenskap . Vol. 41. s. 43–58. doi : 10.1090/dimacs/041/03 . ISBN 9780821808276 . MR 1630408 .