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)=𝔼e^{Xt}$ będzie funkcją tworzącą momenty, niech ${\mathrm{\Lambda }}_X(t)=\ln M_X(t).$

Niech ${\mathrm{\Lambda }}_X^{*}(s)=\sup \{st-{\mathrm{\Lambda }}_X(t):t\in ℝ\}.$

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 $\overline{S_n}=\frac{S_n}{n}.$ Wówczas jeżeli $𝔼X_{+}<\mathrm{\infty }$ lub $𝔼X_{-}<\mathrm{\infty },$ to

$\mathbb{P}(\overline{S_n}⩾s)⩽\exp (-n{\mathrm{\Lambda }}_X^{*}(s))\text{dla}s⩾𝔼X$

oraz

$\mathbb{P}(\overline{S_n}⩽s)⩽\exp (-n{\mathrm{\Lambda }}_X^{*}(s))\text{dla}s⩽𝔼X.$

Szkic dowodu

Zauważmy, że

$\mathbb{P}(\overline{S_n}⩾s)=\mathbb{P}(S_n⩾sn)=\mathbb{P}(e^{t{S}_n}⩾e^{tsn})\stackrel{Markow}{⩽}{e}^{-tsn}𝔼e^{t{S}_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}(\overline{S_n}⩾s)⩽\exp (-n\underset{t⩾0}{\sup }(st-\ln M_X(t)))=\exp (-n{\mathrm{\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)