Bernstein-Ungleichung (Stochastik)

mathematischer Satz

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.

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:

 

Für alle   gilt:

 

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

Beweis (Satz)

Bearbeiten

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

Bearbeiten

Problem 1

Bearbeiten

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

Bearbeiten

Weiterhin seien   und   bekannt.

Es soll gelten:  

Berechne k mit Hilfe der Bernstein-Ungleichung.

 

 

 

Problem 3

Bearbeiten

Seien   und   bekannt.

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

  ?

Man benötigt mindestens   Realisierungen.

Beispiel

Bearbeiten

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

Bearbeiten

Literatur

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