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 |
Excelfunktion [1-POISSON(4;5*0,6;wahr) = 0,185
Beachte:
|
(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