Chernoff-egyenlőtlenség

Magyar

Kiejtés

• IPA: [ ˈhɛrnofːɛɟɛnløːtlɛnʃeːɡ]

Főnév

Chernoff-egyenlőtlenség

1. (matematika, valószínűségszámítás) 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ó.

További információk

• Chernoff-egyenlőtlenség - Értelmező szótár (MEK)
• Chernoff-egyenlőtlenség - Etimológiai szótár (UMIL)
• Chernoff-egyenlőtlenség - Szótár.net (hu-hu)
• Chernoff-egyenlőtlenség - DeepL (hu-de)
• Chernoff-egyenlőtlenség - Яндекс (hu-ru)
• Chernoff-egyenlőtlenség - Google (hu-en)
• Chernoff-egyenlőtlenség - Helyesírási szótár (MTA)
• Chernoff-egyenlőtlenség - Wikidata
• Chernoff-egyenlőtlenség - Wikipédia (magyar)