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 {E} e^{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} \}.$

Przypomnijmy, że $X_{+}=\max\{X,0\}$ i $X_{-}=\max\{-X,0\}$ oznaczają część dodatnią i ujemną zmiennej losowej $X.$ Zachodzi wzór $X=X_{+}-X_{-}.$

Twierdzenie

Niech $X,X_{1},X_{2},\dots ,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 {E} X_{+}<\infty$ lub $\mathbb {E} X_{-}<\infty ,$ to

$\mathbb {P} ({\bar {S_{n}}}\geqslant s)\leqslant \exp(-n\Lambda _{X}^{*}(s))\;{\text{dla}}\;s\geqslant \mathbb {E} X$

oraz

$\mathbb {P} ({\bar {S_{n}}}\leqslant s)\leqslant \exp(-n\Lambda _{X}^{*}(s))\;{\text{dla}}\;s\leqslant \mathbb {E} X.$

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 {Markow}{\leqslant }}e^{-tsn}\mathbb {E} e^{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\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)