Bernstein-Ungleichung (Stochastik)
Die Bernstein-Ungleichung ist eine Abschätzung aus der Wahrscheinlichkeitstheorie und wurde von Sergei Bernstein (1880–1968) bewiesen. Sie ist eine Erweiterung der Hoeffding-Ungleichung, deren Abschätzung durch eine zusätzliche Voraussetzung an die Varianz der Zufallsvariablen verbessert werden kann.

Die Ungleichung gilt für beliebig verteilte beschränkte Zufallsvariablen mit verschwindendem Erwartungswert und beschränkter Varianz.

Satz 

Sei  ein Wahrscheinlichkeitsraum.
Seien  und  positive reelle Zahlen und  eine natürliche Zahl.
 seien unabhängig verteilte Zufallsvariablen mit  und  für alle .

Dann gilt:

Lemma 

Für alle  gilt:

 

Ein Beweis des Lemmas und ein ausführlicherer Beweis des Satzes befinden sich im Beweisarchiv.

Beweis (Satz) 

Dieser Beweis folgt dem Ansatz aus "Support Vector Machines" (siehe Literatur).

Zur Vereinfachung definiere man 

Nach  umgestellt, ergibt sich: 

Nun wird die Ungleichung gezeigt. Man wende die Markow-Ungleichung an mit  und  für ein  (t wird später noch speziell gewählt):

 

Da die Zufallsvariablen nach Voraussetzung unabhängig sind, können Produkt und Erwartungswert vertauscht werden. Aus der Exponentialfunktion bilde man eine unendliche Exponentialreihe. Diese ist durch die integrierbare Majorante  beschränkt. Also können Erwartungswert und Summe vertauscht werden. Mit  und der Voraussetzung  folgt:

 

Mit der Abschätzung  folgt:

 

Durch die Ungleichung  für  erhält man mit :

 

Man setze :

 

Aus dem Lemma (oben) folgt mit .

Anwendung

Problem 1 

Angenommen  und  sind bekannt.

Wie groß ist die Wahrscheinlichkeit höchstens, dass der Mittelwert einen gegebenen Wert k übersteigt?

Löse  nach  auf.

Die Wahrscheinlichkeit, dass der Mittelwert den Wert k übersteigt, ist höchstens .

Problem 2 

Weiterhin seien  und  bekannt.

Es soll gelten: 

Berechne k mit Hilfe der Bernstein-Ungleichung.

Problem 3 

Seien  und  bekannt.

Wie viele Realisierungen werden mindestens benötigt, sodass für gegebene Werte  und  gilt, dass
  ?

Man benötigt mindestens  Realisierungen.

Beispiel 
Als Zufallsvariable betrachte man eine Münze. Den i-ten Münzwurf bezeichnen wir mit . Dabei gelte bei Kopf  und bei Zahl .

Wie groß ist die Wahrscheinlichkeit, dass der Mittelwert nach  Würfen den Wert  übersteigt?

Da die Wahrscheinlichkeit für Kopf und Zahl jeweils 50 % sind, ist der Erwartungswert 0. Da die Zufallsvariablen nur die Werte −1 und 1 annehmen können, kann  gewählt werden.

. Also kann  gewählt werden.

Nun wähle noch . Dabei ist  die Anzahl der Münzwürfe.
Nach der Bernstein-Ungleichung gilt dann:

 

Also gilt zum Beispiel bei 50 Würfen:

 

Damit der Mittelwert  übersteigt, müsste man bei 50 Würfen 31-mal Kopf werfen.

 

Das heißt, die Wahrscheinlichkeit, in 50 Würfen 31 Kopf zu erhalten, ist kleiner als

Siehe auch 
 Tschebyschow-Ungleichung

Literatur 
 Ingo Steinwart, Andreas Christmann: Support Vector Machines. Information Science and Statistics. 1. Auflage. Springer, Berlin 2008

Weblinks 

Zufallsvariable
Satz (Mathematik)
Ungleichung (Stochastik)