Hoeffding Ungleichung

Näherungsgleichung für eine obere Schranke der Wahrscheinlichkeit, dass die Summe mehrerer Zufallsvariablen X_i nicht mehr als eine vorgegebene Konstante c vom Erwartungswert der Summe abweicht.

Die angegebene Formel ist eine Vereinfachung. Die Zufallsvariablen Xi sind so zu skalieren, dass ihre Erwartungswert jeweils 0 ergeben. ( Zentrierung)  ai und bi sind diejenigen Schranken, innerhalb derer die Ausprägungen der Zufallsvariablen Xi auf jeden Fall zu liegen kommen.

Beispiel 

Ein idealer Würfel wird 1000 Mal geworfen (Augenzahlen 1,2,3,4,5,6). 

In diesem Beispiel handelt es sich um 1000 unabhängige, aber identische Zufallsvariablen, 

deren Ausprägungen 1,2,3,4,5 oder 6 betragen können.

Der Erwartungswert der Summe aller Augenzahlen beträgt (1+2+3+4+5+6)/6 *1000 = 3500. 

Wie gross ist die Wahrscheinlichkeit, dass die Summe der Augenzahlen bei 1000 Würfen mindestens 

1. 4000 

2. 3600

3. 3500    beträgt? 

zu 1. 

Der Erwartungswert für einen Wurf liegt bei 3,5. Die Schranken bei 1 und 6.  

Verschieben der Skala um 3,5 sodass der Erwartungswert bei 0 zu liegen kommt, führt auf die Schranken -2,5 und +2,5.

Also c= (4000-3500)=500, a_i = -2,5 und b_i = +2,5. 

Eingesetzt in obige Formel: 

= 2,1E-9 

entsprechend 2. und 3. 

= 0.45

= 1 

Achtung: bei den Ergebnissen handelt es sich um obere Schranken. 

Siehe auch Chernoff Ungleichung