Nierówność Azumy

W teorii prawdopodobieństwa nierówność Azumy – Hoeffdinga (nazwana na cześć Kazuokiego Azumy i Wassily'ego Hoeffdinga ) daje wynik koncentracji dla wartości martyngałów , które mają ograniczone różnice.

Załóżmy, że ${\ Displaystyle \ {X_ {k}: k = 0,1,2,3, \ kropki \}}$ jest martyngałem (lub super-martyngałem ) I

${\ Displaystyle | X_ {k} -X_ {k-1} | \ równoważnik c_ {k}, \,}$

prawie na pewno . Następnie dla wszystkich dodatnich liczb całkowitych N i wszystkich dodatnich liczb rzeczywistych ${\ Displaystyle \ epsilon}$ ,

${\ Displaystyle {\ text {P}} (X_ {N} -X_ {0} \ geq \ epsilon) \ równoważnik \ exp \ lewo ({- \ epsilon ^ {2} \ ponad 2 \ suma _ {k = 1 }^{N}c_{k}^{2}}\prawo).}$

I symetrycznie (gdy X _k jest podmartyngałem):

${\ Displaystyle {\ tekst {P}} (X_ {N} -X_ {0} \ równoważnik - \ epsilon) \ równoważnik \ exp \ lewo ({- \ epsilon ^ {2} \ ponad 2 \ suma _ {k = 1}^{N}c_{k}^{2}}\prawo).}$

Jeśli X jest martyngałem, użycie obu powyższych nierówności i zastosowanie związku sumy pozwala uzyskać dwustronną granicę:

${\ Displaystyle {\ tekst {P}} (| X_ {N} -X_ {0} | \ geq \ epsilon) \ równoważnik 2 \ exp \ lewo ({- \ epsilon ^ {2} \ ponad 2 \ suma _ { k=1}^{N}c_{k}^{2}}\prawo).}$

Dowód

Dowód ma podobną ideę dowodu dla ogólnej postaci nierówności Azumy wymienionej poniżej. W rzeczywistości można to postrzegać jako bezpośrednią konsekwencję ogólnej postaci nierówności Azumy.

Ogólna postać nierówności Azumy

Ograniczenie waniliowej nierówności Azumy

Zauważ, że nierówność wanilii Azumy wymaga symetrycznych granic przyrostów martyngałów, tj. ${\ Displaystyle -c_ {t} \ równoważnik X_ {t} -X_ {t-1} \ leq c_{t}}$ . Tak więc, jeśli znana granica jest asymetryczna, np. ${\ Displaystyle a_ {t} \ równoważnik X_ {t} -X_ {t-1} \ równoważnik b_ {t}$ } do ${\ Displaystyle c_ {t} = \ max (| a_ {t} |, | b_ {t} |)$ co może być stratą informacji o ograniczoności ${\ Displaystyle X_ {t} -X_ {t-1}}$ . Jednak ten problem można rozwiązać i uzyskać ściślejsze prawdopodobieństwo związane z następującą ogólną postacią nierówności Azumy.

Oświadczenie

Niech ${\ Displaystyle \ lewo \ {X_ {0}, X_ {1}, \ cdots \ prawo \}}$ będzie martyngałem (lub supermartyngałem) w odniesieniu do filtracji ${\ Displaystyle \ lewo \ {{\ mathcal {F}} _ {0}, {\ mathcal {F}} _ {1}, \ cdots \ prawo \}}$ . $_$ istnieją procesy _ $_ lewo \ {B_ {0}, B_ {1} \ kropki \ prawo \}}$ w odniesieniu do ${\ Displaystyle \ lewo \ {{\ mathcal {F}} _ {0}, {\ mathcal {F}} _ {1}, \ cdots$$prawo$ } $,$ . dla ${\ Displaystyle {\ mathcal {F}} _ {t-1}}$ - mierzalne i stałe ${\ Displaystyle 0 <c_ {1}, c_ {2}, \cdots <\infty }$ takie, że

${\ Displaystyle A_ {t} \ równoważnik X_ {t} -X_ {t-1} \ równoważnik B_ {t} \ quad {\text{and}}\quad B_{t}-A_{t}\równoważnik c_{t}}$

prawie na pewno. Wtedy dla wszystkich ${\ displaystyle \ epsilon > 0}$ ,

${\ Displaystyle {\ text {P}} (X_ {n} -X_ {0} \ geq \ epsilon) \ równoważnik \ exp \ lewo (- {\ Frac {2 \ epsilon ^ {2}} {\ suma _ { t=1}^{n}c_{t}^{2}}}\prawo).}$

$tego$ supermartyngałem z odwróconymi znakami martyngałem lub podmartyngał),

${\ Displaystyle {\ text {P}} (X_ {n} -X_ {0} \ równoważnik - \ epsilon) \ równoważnik \ exp \ lewo (- {\ Frac {2 \ epsilon ^ {2}} {\ suma _ {t=1}^{n}c_{t}^{2}}}\prawo).}$

Jeśli $jest$ martyngałem, ponieważ jest zarówno nadmartyngałem do dwóch powyższych nierówności moglibyśmy otrzymać dwustronne ograniczenie:

${\ Displaystyle {\ tekst {P}} (| X_ {n} -X_ {0} | \ geq \ epsilon) \ równoważnik 2 \ exp \ lewo (- {\ Frac {2 \ epsilon ^ {2}} {\ suma _{t=1}^{n}c_{t}^{2}}}\prawo).}$

Dowód

Udowodnimy przypadek supermartyngału tylko dlatego, że reszta jest oczywista. Przez rozkład Dooba $Y_ {t$ rozłożyć supermartingale jako $t$ gdzie ${\ Displaystyle \ lewo \ {Y_ {t}, {\ mathcal {F}} _ {t} \ prawej \}}$ jest martyngałem i ${\ Displaystyle \ lewo \ {Z_ {t}, {\ mathcal {F}} _ {t} \ prawo \}} jest nierosnącą$ przewidywalną sekwencją (Zauważ, że jeśli ${\ Displaystyle \ lewo \ { X_ {t} \ prawo \}}$ samo w sobie jest martyngałem, więc ${\ displaystyle Z_ {t} = 0}$ ). ZA ${\ Displaystyle A_ {t} \ równoważnik X_ {t} -X_ {t-1} \ równoważnik B_ {t$ }

${\ Displaystyle - (Z_ {t} -Z_ {t-1 })+A_{t}\leq Y_{t}-Y_{t-1}\leq -(Z_{t}-Z_{t-1})+B_{t}}$

Stosując Chernoff związany z , mamy dla ϵ > {\ displaystyle \ epsilon > 0}, $}$$Y {\ Displaystyle Y_$ {

${\ Displaystyle {\ rozpocząć {wyrównane} {\ tekst {P}} (Y_ {n} -Y_ {0} \ geq \ epsilon) i \ leq {\ underset {s >0}{\min }}\ e^{-s\epsilon }\mathbb {E} [e^{s(Y_{n}-Y_{0})}]\\&={\underset {s> 0}{\min }}\ e^{-s\epsilon }\mathbb {E} \left[\exp \left(s\sum _{t=1}^{n}(Y_{t}-Y_{ t-1})\right)\right]\\&={\underset {s>0}{\min }}\ e^{-s\epsilon }\mathbb {E} \left[\exp \left( s\sum _{t=1}^{n-1}(Y_{t}-Y_{t-1})\right)\mathbb {E} \left[\exp \left(s(Y_{n} -Y_{n-1}\right)\mid {\mathcal {F}}_{n-1}\right]\right]\end{aligned}}}$

Dla wewnętrznego terminu oczekiwania, ponieważ (i) ${\ Displaystyle \ mathbb {E} [Y_ {n} -Y_ {n-1} \ mid {\ mathcal {F}} _ {n-1}] = 0}$ ponieważ ${\ Displaystyle \ lewo \ {Y_ {n} \ prawo \}}$ jest martyngałem; (ii) ${\ Displaystyle - (Z_ {n} -Z_ { n-1})+A_{n}\równik Y_{n}-Y_{n-1}\równik -(Z_{n}-Z_{n-1})+B_{n}}$ ; (iii) ${\ Displaystyle - (Z_ {n} -Z_ {n-1}) + A_ {n}}$ i ${\ Displaystyle - (Z_ {n} -Z_ {n-1}) + B_ {n}}$ oba są ${\ Displaystyle {\ mathcal {F}} _ {n-1}}$ - mierzalny, ponieważ ${Z_ {t} \ prawo \}}$ procesem przewidywalnym; i (iv) ${\ Displaystyle B_ {n} -A_ {n} \ równoważnik c_ {n}}$ , stosując lemat Hoeffdinga , mamy

${\ Displaystyle \ mathbb {E} \ lewo [\ exp \ lewo (s (Y_ {n} -Y_ {n-1}) \ mid {\ mathcal {F}} _ {n-1} \ prawo) \ prawo ]\leq \exp \left({\frac {s^{2}(B_{n}-A_{n})^{2}}{8}}\right)\leq \exp \left({\frac {s^{2}c_{n}^{2}}{8}}\prawo).}$

Powtarzając ten krok, można uzyskać

${\ Displaystyle {\ text {P}} (Y_ {n} -Y_ {0} \ geq \ epsilon) \ leq {\ underset {s> 0} {\ min}} \ e ^ {-s \ epsilon} \ exp \left({\frac {s^{2}\sum _{t=1}^{n}c_{t}^{2}}{8}}\right).}$

${2}}}}$${\ Displaystyle s = {\ Frac {4 \ epsilon}} {\ suma _ {t = 1} ^ {n} c_ {t}$ ^ , więc mamy

${\ Displaystyle {\ text {P}} (Y_ {n} -Y_ {0} \ geq \ epsilon) \ równoważnik \ exp \ lewo (- {\ Frac {2 \ epsilon ^ {2}} {\ suma _ { t=1}^{n}c_{t}^{2}}}\prawo).}$

$\ Displaystyle X_ {n} -X_ {0} = (Y_ {n} -Y_ {0}) + (Z_ {n } -Z_ {0})}$ Z i ${\ Displaystyle Z_ {n} -Z_ {0} \ równoważnik 0}$ jak ${\ Displaystyle \ lewo \ {Z_ {n} \ prawo \} }$ nie rośnie, więc zdarzenie ${\ Displaystyle \ lewo \ {X_ {n} -X_ {0} \ geq \ epsilon \ prawo \}}$ implikuje ${\ styl wyświetlania \left\{Y_{n}-Y_{0}\geq \epsilon \right\}}$ , a zatem

${\ Displaystyle {\ tekst {P}} (X_ {n} -X_ {0} \ geq \ epsilon) \ równoważnik {\ tekst {P}} (Y_ {n} -Y_ {0} \ geq \ epsilon) \leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).\square }$

Uwaga

$_$ ustawiając _

Zauważ, że w przypadku podmartyngału lub supermartyngału zachodzi tylko jedna strona nierówności Azumy. Niewiele możemy powiedzieć o tym, jak szybko rośnie podmartyngał z ograniczonymi przyrostami (lub spada supermartyngał).

Ta ogólna postać nierówności Azumy zastosowana do martyngału Doob daje nierówność McDiarmida , która jest powszechna w analizie losowych algorytmów .

Prosty przykład nierówności Azumy dla rzutów monetą

Niech F _i będzie sekwencją niezależnych i identycznie rozłożonych losowych rzutów monetą (tzn. niech F _i będzie z równym prawdopodobieństwem −1 lub 1 niezależnie od innych wartości Fi ₎ . Zdefiniowanie ${\ Displaystyle X_ {i} = \ suma _ {j = 1} ^ {i} F_ {j}}$ daje martyngał z | X _k - X _{k -1} | ≤ 1, co pozwala nam zastosować nierówność Azumy. Konkretnie dostajemy

${\ Displaystyle {\ tekst {P}} (X_ {n}> t) \ równoważnik \ exp \ lewo ({\ Frac {-t ^ {2}} {2n}} \ prawo).}$

Na przykład, jeśli ustawimy t proporcjonalnie do n , to mówi nam to, że chociaż maksymalna możliwa wartość X _n skaluje się liniowo z n , prawdopodobieństwo , że suma skaluje się liniowo z n maleje wykładniczo szybko z n .

Jeśli ustawimy ${\ Displaystyle t = {\ sqrt {2n \ ln n}}}$ otrzymamy:

${\ Displaystyle {\ tekst {P}} (X_ {n}> {\ sqrt {2n \ ln n}}) \ równoważnik 1/n}$

$,$ że ​​prawdopodobieństwo odchylenia o więcej niż gdy n dąży do nieskończoności

Uwaga

Podobną nierówność przy słabszych założeniach udowodnił Siergiej Bernstein w 1937 roku.

Hoeffding udowodnił ten wynik dla zmiennych niezależnych, a nie różnic martyngałowych, a także zauważył, że niewielkie modyfikacje jego argumentu ustalają wynik dla różnic martyngałowych (patrz strona 9 jego artykułu z 1963 r.).

Zobacz też

• Nierówność koncentracji - podsumowanie granic ogona dla zmiennych losowych.

Notatki

• Alon, N.; Spencer, J. (1992). Metoda probabilistyczna . Nowy Jork: Wiley.
•   Azuma, K. (1967). „Ważone sumy niektórych zależnych zmiennych losowych” (PDF) . Dziennik matematyczny Tôhoku . 19 (3): 357–367. doi : 10.2748/tmj/1178243286 . MR 0221571 .
• Bernstein, Siergiej N. (1937). На определенных модификациях неравенства Чебишева [O pewnych modyfikacjach nierówności Czebyszewa]. Doklady Akademii Nauk SSSR (po rosyjsku). 17 (6): 275–277. (t. 4, poz. 22 w zbiorach)
•   McDiarmid, C. (1989). „O metodzie różnic ograniczonych”. Badania w kombinatoryce . Matematyka Londynu. soc. Wykłady Notatki 141. Cambridge: Cambridge Univ. Naciskać. s. 148–188. MR 1036755 .
•    Hoeffding, W. (1963). „Nierówności prawdopodobieństwa dla sum ograniczonych zmiennych losowych” . Dziennik Amerykańskiego Towarzystwa Statystycznego . 58 (301): 13–30. doi : 10.2307/2282952 . JSTOR 2282952 . MR 0144363 .
•    Godbole, AP; Hitchenko, P. (1998). Poza metodą różnic ograniczonych . Seria DIMACS w matematyce dyskretnej i informatyce teoretycznej . Tom. 41. s. 43–58. doi : 10.1090/dimacs/041/03 . ISBN 9780821808276 . MR 1630408 ​​.