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 ${\displaystyle M_{X}(t)=\mathbb {E} e^{Xt}}$ będzie funkcją tworzącą momenty, niech ${\displaystyle \Lambda _{X}(t)=\ln M_{X}(t).}$

Niech ${\displaystyle \Lambda _{X}^{*}(s)=\sup\{st-\Lambda _{X}(t):t\in \mathbb {R} \}.}$

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

Twierdzenie

Niech ${\displaystyle X,X_{1},X_{2},\dots ,X_{n}}$ będą niezależnymi zmiennymi losowymi, ${\displaystyle S_{n}=\sum _{i=1}^{n}X_{i}}$ oraz ${\displaystyle {\bar {S_{n}}}={\frac {S_{n}}{n}}.}$ Wówczas jeżeli ${\displaystyle \mathbb {E} X_{+}<\infty }$ lub ${\displaystyle \mathbb {E} X_{-}<\infty ,}$ to

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

oraz

${\displaystyle \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

${\displaystyle \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 ${\displaystyle t,}$ to mamy również

${\displaystyle \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)