Chernoff-egyenlőtlenség

(Csernov-egyenlőtlenség szócikkből átirányítva)

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.[1][2]

Állítás szerkeszté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 szerkesztés

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 szerkesztés

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 szerkeszté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 szerkesztés

  1. Herman Csernov.szerk.: Xihong Lin, Christian Genest, David L. Banks, Geert Molenberghs, David W. Scott, Jane-Ling Wang: A career in statistics.. CRC Press (2014). ISBN 9781482204964 
  2. John Bather (1996. 11). „A Conversation with Herman Chernoff”. Statistical Science 11 (4), 335-350. o. DOI:10.1214/ss/1032280306.  

Források szerkesztés

Fordítás szerkesztés

Ez a szócikk részben vagy egészben a Chernoff-Ungleichung című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.