Nierówność Chernoffa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Nierówność Chernoffa dostarcza silnych oszacowań prawdopodobieństwa, że suma jednakowych niezależnych zmiennych losowych przekracza pewną liczbę rzeczywistą.

Definicje[edytuj | edytuj kod]

Aby sformułować jasno nierówność Chernoffa należy wcześniej zdefiniować parę pojęć. Niech M_X(t)=\mathbb Ee^{Xt} będzie funkcją tworzącą momenty, niech \Lambda_X(t)=\ln M_X(t)\!.

Niech \Lambda^*_X(s)=\sup\{st-\Lambda_X(t):t\in\mathbb R\}.

Twierdzenie[edytuj | edytuj kod]

Niech X,X_1,X_2,\ldots,X_n będą niezależnymi zmiennymi losowymi, S_n=\sum_{i=1}^n X_i oraz \bar{S_n}=\frac{S_n}{n}. Wówczas jeżeli \mathbb EX_+<\infty lub \mathbb EX_-<\infty, to

\mathbb P(\bar{S_n}\geqslant s)\leqslant \exp(-n\Lambda^*_X(s))\ dla\ s\geqslant\mathbb EX

oraz

\mathbb P(\bar{S_n}\leqslant s)\leqslant \exp(-n\Lambda^*_X(s))\ dla\ s\leqslant\mathbb EX

Szkic dowodu[edytuj | edytuj kod]

Zauważmy, że

\mathbb P(\bar{S_n}\geqslant s)=\mathbb P(S_n\geqslant sn)=\mathbb P(e^{tS_n}\geqslant e^{tsn})\stackrel{Czeb.}{\leqslant} e^{-tsn}\mathbb Ee^{tS_n}=e^{-tsn}(M_X(t))^n=\exp(-n(st-\ln M_X(t)))

Ponieważ lewa strona nie jest zależna od zmiennej t, to mamy również

\mathbb P(\bar{S_n}\geqslant s)\leqslant\exp(-n\sup_{t\geqslant 0}(st-\ln M_X(t)))=\exp(-n\sup_{t\geqslant 0}(\Lambda^*_X(s)))

Pozostała część dowodu nierówności to szczegóły techniczne.

Bibliografia[edytuj | edytuj kod]