Nierówność Chernoffa

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

Definicje

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

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

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

• Skrypt do rachunku prawdopodobieństwa (w przypadku wystąpienia błędu 403 należy umieścić kursor w polu adresu i wcisnąć klawisz Enter)