# Chernoff Ungleichung

## Näherung der Binomialverteilung für grosse Zahlen

Ohne Frames
Bei der Binomialverteilung kommt man für grosse Anzahlen in Rechenschwierigkeiten. Zwar bietet sich dann die Poissonverteilung als Alternative an, doch diese stellt eine wichtige Nebenbedingung. Die Chernoff Ungleichung dagegen gestattet eine sehr einfache, wenn auch überaus konservative (und damit manchmal wertlose) Abschätzung.

zurück zum Glossar (Chernoff)

Chernoff Ungleichung

Sehr konservative Näherungsgleichung für die Wahrscheinlichkeit, mit der die Anzahl erwünschter Ereignisse eines wiederholten Bernoulli-Experiments vom theoretischen Erwartungswert abweicht. -> Also eine Näherung für die Anzahl erwünschter Ereignisse bei Binomialverteilung.

Eine alternative Näherungsmethode ist die Poissonverteilung. Eine graphische Methode ist das Larson Nomogramm.

Während die Poissoverteilung grosse Anzahlen Ereignisse n bei gleichzeitig kleinen Einzelwahrscheinlichkeiten p, zusätzlich n*p>9 fordert, verlangt die Chernoff Ungleichung lediglich grosse Anzahlen Ereignisse n und ist dabei noch einfacher zu berechnen.

Allerdings liefert die Chernoff Ungleichung lediglich eine obere Schranke.

In der Informationstheorie oft angewendete Ungleichung.

Die beiden Varianten der Chernoff Ungleichung lauten:

, für delta > 0

, , für 0 < delta < 1

Beispiel 1

5 Mal Ziehen mit Zurücklegen aus einer Urne mit 6 schwarzen und 4 weissen Kugeln (p = 0,6 und q = 0,4)

Wie gross ist die Wahrscheinlichkeit, dass mindestens 4 Schwarze dabei sind? ---> x=4 und n=5.

Erwartungswert: =3. Einzelwahrscheinlichkeit p: = 0,6

Exakte Berechnung | Näherungsweise Berechnung
Binomialverteilung | Poissonverteilung | Chernoff Ungleichung
Excelfunktion [1-BINOMVERT(4;5;0,6;wahr)] = 0,0778 | Excel funktion [1-POISSON(4;5*0,6;wahr) = 0,185 Beachte: µ=n*p =5*0,6 =3 > 9 ist nicht erfüllt. p-> 0 ist nicht erfüllt. | (1+delta)*pn muss 4 ergeben -> d=1/3. -> P<0,895

Beispiel 2

50 Mal Ziehen mit Zurücklegen aus einer Urne mit 6 schwarzen und 4 weissen Kugeln (p = 0,6 und q = 0,4)

Wie gross ist die Wahrscheinlichkeit, dass mindestens 40 Schwarze dabei sind? ---> x=40 und n=50.

Erwartungswert: =3. Einzelwahrscheinlichkeit p: = 0,6

Exakte Berechnung | Näherungsweise Berechnung
Binomialverteilung | Poissonverteilung | Chernoff Ungleichung
Excelfunktion [1-BINOMVERT(40;50;0,6;wahr)] = 0,000757 | Excelfunktion [1-POISSON(40;50*0,6;wahr) = 0,0323 Beachte: p -> 0 ist hier nicht erfüllt. | (1+delta)*pn muss 40 ergeben -> d=1/3. -> P<0,329

Beispiel 3

50 Mal Ziehen mit Zurücklegen aus einer Urne mit 5 schwarzen und 95 weissen Kugeln (p = 0,05 und q = 0,95)

Wie gross ist die Wahrscheinlichkeit, dass mindestens 4 Schwarze dabei sind? ---> x=4 und n=50.

Erwartungswert: =2,5. Einzelwahrscheinlichkeit p: = 0,05

Exakte Berechnung | Näherungsweise Berechnung
Binomialverteilung | Poissonverteilung | Chernoff Ungleichung
Excelfunktion [1-BINOMVERT(4;50;0,05;wahr)] = 0,104 | Excelfunktion [1-POISSON(4;50*0,05;wahr) = 0,109 | (1+delta)*pn muss 4 ergeben -> d=0,6. -> P<0,741

Beispiel 4

50 Mal Ziehen mit Zurücklegen aus einer Urne mit 5 schwarzen und 95 weissen Kugeln (p = 0,05 und q = 0,95)

Wie gross ist die Wahrscheinlichkeit, dass mindestens 40 Schwarze dabei sind? ---> x=40 und n=50.

Erwartungswert: =2,5. Einzelwahrscheinlichkeit p: = 0,05

Exakte Berechnung | Näherungsweise Berechnung
Binomialverteilung | Poissonverteilung | Chernoff Ungleichung
Excelfunktion [1-BINOMVERT(40;50;0,05;wahr)] =1,887 E-15 | Excelfunktion [1-POISSON(40;50*0,05;wahr) = 0 | (1+delta)*pn muss 40 ergeben -> d=15. -> P<3,73 E-6

Wie man aus den obigen Beispielen erkennen kann, ist die Chernoff Ungleichung sehr konservativ.

Siehe auch Hoeffding Ungleichung.

21.09.2005

zurück zum Glossar (Chernoff)