Chernoff-egyenlőtlenség

1. Sablon:Humatek 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ó.