I sannolikhetsteorin ger Azuma–Hoeffding-ojämlikheten (uppkallad efter Kazuoki Azuma och Wassily Hoeffding) ett koncentrationsresultat för värdena på 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
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.
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