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:

Chernoff Ungleichung, für delta > 0

Chernoff Ungleichung,      , 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

Excelfunktion

[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.

Chernoff Ungleichung Beispiel

-> 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.

Chernoff Ungleichung Beispiel

-> 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.

Chernoff Ungleichung Beispiel

-> 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.

Chernoff Ungleichung Beispiel

-> 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)

Datenschutzhinweise