A Chernoff-egyenlőtlenség a valószínűségszámításban felső korlátot ad meg arra, hogy Bernoulli-eloszlású valószínűségi változókkal végzett kísérletek sorozatában a sikeres kísérletek száma mennyire tér el a várható értéktől. Az informatikában a véletlenített algoritmusok elemzéséhez is sokoldalúan és sokszor használják. Herman Chernoffról nevezték el, de már Herman Rubin is ismerte.
Állítás Legyen független Bernoulli-kísérlet, ahol és ! Ekkor a sikeres kísérletek száma, ahol a kísérlet sikeres, ha .
1. Minden esetén
2. és minden esetén:
Általánosítása Legyenek diszkrét, független valószínűségi változók, úgy, hogy und . Legyen szórásnégyzete. Ekkor minden esetén:
Ennek bizonyítása a nem általánosított változatéhoz hasonló. Példák Az első példa kérdése: Mekkora annak az esélye, hogy egy szabályos érmét tízszer feldobva legalább hétszer írást kapunk?
Legyenek az érmedobásoknak megfelelő Bernoulli-kísérletek, ahol . Az első Csernov-egyenlőtlenség szerint
így
A második példa kérdése: Mekkora annak az esélye, hogy egy szabályos érmét százszor feldobva legalább hetvenszer írást kapunk?
Az első Csernov-korlát itt már erősebb becslést ad:
Bizonyítás Legyen tetszőleges konstans, és vezessük be az valószínűségi változót az írásmód könnyítésére úgy, hogy ! Az monoton volta miatt , ahol és az utolsó becslés a Markov-egyenlőtlenségből következik. Ekkor
így . Továbbá . Mivel tetszőleges, azért ez esetén is teljesül. Ezzel . A jobb oldal kitevőjének egy részére . Görbediszkusszióval és Taylor-sorfejtéssel megmutatható, hogy Az exponenciális függvény monotóniájára hivatkozva . Az első becsléssel együtt következik az első állítás.
A második állítás hasonlóan látható be.
Jegyzetek
Források Christian Schindelhauer, Algorithmen für Peer-to-Peer Netzwerke (Vorlesungsmaterialien), https://web.archive.org/web/20060822073416/http://wwwcs.upb.de/cs/ag-madh/WWW/Teaching/2004SS/AlgoP2P/skript.html, Universität Paderborn, 2004. Kirill Levchenko, Notizen, http://www.cs.ucsd.edu/~klevchen/techniques/chernoff.pdf
Fordítás
Kategória:Valószínűségszámítás