Chernoff-egyenlőtlenség

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 $X_1,X_2,\dots ,X_n$ $n$ független Bernoulli-kísérlet, ahol $P[X_i=1]=p$ és $P[X_i=0]=1-p$! Ekkor $pn$ a sikeres kísérletek száma, ahol a kísérlet sikeres, ha $X_i=1$.

1. Minden $\delta >0$ esetén

$P[\sum X_i\ge (1+\delta )\cdot pn]\le \exp (-\frac{\min \{\delta ,{\delta }^2\}}{3}pn)$

2. és minden $\delta \in [0,1]$ esetén:

$P[\sum X_i\le (1-\delta )\cdot pn]\le \exp (-\frac{{\delta }^2}{2}pn)$

Általánosítása

Legyenek $X_1,X_2,\dots ,X_n$ diszkrét, független valószínűségi változók, úgy, hogy $\text{E}[X_i]=0$ und $|X_i|\le 1$. Legyen ${\sigma }^2$ $X=\sum X_i$ szórásnégyzete. Ekkor minden $0<\lambda \le 2\sigma$ esetén:

$P[|\sum X_i|\ge \lambda \sigma ]\le 2\exp (-\frac{{\lambda }^2}{4})$

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 $X_1,X_2,\dots ,X_{10}$ az érmedobásoknak megfelelő Bernoulli-kísérletek, ahol $pn=\frac{1}{2}\cdot 10=5$. Az első Csernov-egyenlőtlenség szerint

$P[\sum X_i\ge 7]=P[\sum X_i\ge (1+\frac{4}{10})\cdot 5]$

így

$\le \exp (-\frac{\min \{\frac{4}{10},\frac{16}{100}\}}{3}\cdot 5)=\exp (-\frac{4}{15})\approx 0,766\dots$

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:

$P[\sum X_i\ge 70]=P[\sum X_i\ge (1+\frac{4}{10})\cdot 50]$

$\le \exp (-\frac{\min \{\frac{4}{10},\frac{16}{100}\}}{3}\cdot 50)=\exp (-\frac{8}{3})\approx 0,069\dots$

Bizonyítás

Legyen $t>0$ tetszőleges konstans, és vezessük be az $Y$ valószínűségi változót az írásmód könnyítésére úgy, hogy $Y=\exp (t\sum X_i)$! Az $x\mapsto \exp (tx)$ monoton volta miatt

$P[\sum X_i\ge (1+\delta )\cdot pn]=P[Y\ge \exp (t(1+\delta )\cdot pn)]=P[Y\ge k\text{E}\left[Y\right]]\le \frac{1}{k}$,

ahol $k=\frac{\exp (t(1+\delta )pn)}{\text{E}[Y]}$ és az utolsó becslés a Markov-egyenlőtlenségből következik. Ekkor

$\text{E}[\exp (t{X}_i)]=(1-p)e^0+p{e}^t=1+(e^t-1)p$

így

$\text{E}\left[Y\right]=\text{E}[\exp (t\sum X_i)]=\text{E}[\prod \exp (t{X}_i)]=\prod \text{E}[\exp (t{X}_i)]={(1+(e^t-1)p)}^n$.

Továbbá

$\frac{1}{k}=e^{-t(1+\delta )pn}{(1+(e^t-1)p)}^n\le e^{-t(1+\delta )pn}\cdot e^{(e^t-1)pn}=e^{-t(1+\delta )pn+(e^t-1)pn}$.

Mivel $t$ tetszőleges, azért ez $t=\log (1+\delta )$ esetén is teljesül. Ezzel

$\frac{1}{k}\le e^{-(\log (1+\delta ))(1+\delta )pn+\delta pn}=e^{(\delta -(1+\delta )\log (1+\delta ))pn}$.

A jobb oldal kitevőjének egy részére

$L(\delta )=(1+\delta )\log (1+\delta )$.

Görbediszkusszióval és Taylor-sorfejtéssel megmutatható, hogy $L(\delta )\ge \delta +\frac{1}{3}\min \{\delta ,{\delta }^2\}$ Az exponenciális függvény monotóniájára hivatkozva

$\frac{1}{k}\le e^{(\delta -(\delta +\frac{1}{3}\min \{\delta ,{\delta }^2\}))pn}=\exp (-\frac{\min \{\delta ,{\delta }^2\}}{3}pn)$.

Az első becsléssel együtt következik az első állítás.

A második állítás hasonlóan látható be.

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