Z Wikipedii, wolnej encyklopedii
Nierówność Chernoffa dostarcza silnych oszacowań prawdopodobieństwa, że suma jednakowych niezależnych zmiennych losowych przekracza pewną liczbę rzeczywistą.
Aby sformułować jasno nierówność Chernoffa, należy wcześniej zdefiniować parę pojęć. Niech
będzie funkcją tworzącą momenty, niech
Niech
Przypomnijmy, że
i
oznaczają część dodatnią i ujemną zmiennej losowej
Zachodzi wzór
Niech
będą niezależnymi zmiennymi losowymi,
oraz
Wówczas jeżeli
lub
to
![{\displaystyle \mathbb {P} ({\bar {S_{n}}}\geqslant s)\leqslant \exp(-n\Lambda _{X}^{*}(s))\;{\text{dla}}\;s\geqslant \mathbb {E} X}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4b198172250774cce35127dc31a2853b3b6d6e3)
oraz
![{\displaystyle \mathbb {P} ({\bar {S_{n}}}\leqslant s)\leqslant \exp(-n\Lambda _{X}^{*}(s))\;{\text{dla}}\;s\leqslant \mathbb {E} X.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b07d24ee48ae5956a6f58b9e73d647c42a18d03e)
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))).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7134026025ec59f99aa0102cac111b2e01e38bab)
Ponieważ lewa strona nie jest zależna od zmiennej
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)).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7f3c3ddf61a0fe6111f164d66b15538576beaca)
Pozostała część dowodu nierówności to szczegóły techniczne.