Nierówność Chernoffa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Nierówność Chernoffa dostarcza silnych oszacowań prawdopodobieństwa, że suma jednakowych niezależnych zmiennych losowych przekracza pewną liczbę rzeczywistą.

Definicje[edytuj]

Aby sformułować jasno nierówność Chernoffa należy wcześniej zdefiniować parę pojęć. Niech będzie funkcją tworzącą momenty, niech .

Niech .

Twierdzenie[edytuj]

Niech będą niezależnymi zmiennymi losowymi, oraz . Wówczas jeżeli lub , to

oraz

Szkic dowodu[edytuj]

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.

Bibliografia[edytuj]