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},\ldots ,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\left[\sum X_{i}\geq (1+\delta )\cdot pn\right]\leq \exp \left(-{\frac {\min\{\delta ,\delta ^{2}\}}{3}}pn\right)$

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

$P\left[\sum X_{i}\leq (1-\delta )\cdot pn\right]\leq \exp \left(-{\frac {\delta ^{2}}{2}}pn\right)$

Általánosítása

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

$P\left[\left|\sum X_{i}\right|\geq \lambda \sigma \right]\leq 2\exp \left(-{\frac {\lambda ^{2}}{4}}\right)$

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},\ldots ,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\left[\sum X_{i}\geq 7\right]=P\left[\sum X_{i}\geq \left(1+{\frac {4}{10}}\right)\cdot 5\right]$

így

$\leq \exp \left(-{\frac {\min\{{\frac {4}{10}},{\frac {16}{100}}\}}{3}}\cdot 5\right)=\exp \left(-{\frac {4}{15}}\right)\approx 0{,}766\ldots$

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\left[\sum X_{i}\geq 70\right]=P\left[\sum X_{i}\geq \left(1+{\frac {4}{10}}\right)\cdot 50\right]$

$\leq \exp \left(-{\frac {\min\{{\frac {4}{10}},{\frac {16}{100}}\}}{3}}\cdot 50\right)=\exp \left(-{\frac {8}{3}}\right)\approx 0{,}069\ldots$

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 $\textstyle Y=\exp \left(t\sum X_{i}\right)$! Az $x\mapsto \exp(tx)$ monoton volta miatt

$P\left[\sum X_{i}\geq (1+\delta )\cdot pn\right]=P\left[Y\geq \exp \left(t(1+\delta )\cdot pn\right)\right]=P\left[Y\geq k{\textrm {E}}\left[Y\right]\right]\leq {\frac {1}{k}}$,

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

${\textrm {E}}\left[\exp(tX_{i})\right]=(1-p)e^{0}+pe^{t}=1+(e^{t}-1)p$

így

${\textrm {E}}\left[Y\right]={\textrm {E}}\left[\exp(t\sum X_{i})\right]={\textrm {E}}\left[\prod \exp(tX_{i})\right]=\prod {\textrm {E}}\left[\exp(tX_{i})\right]=\left(1+(e^{t}-1)p\right)^{n}$.

Továbbá

${\frac {1}{k}}=e^{-t(1+\delta )pn}\left(1+(e^{t}-1)p\right)^{n}\leq 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}}\leq 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 )\geq \delta +{\tfrac {1}{3}}\min\{\delta ,\delta ^{2}\}$ Az exponenciális függvény monotóniájára hivatkozva

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

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

Fordítá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.