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
oraz
Zauważmy, że
Ponieważ lewa strona nie jest zależna od zmiennej to mamy również
Pozostała część dowodu nierówności to szczegóły techniczne.