Beweisarchiv: Stochastik
- Statistik: Arithmetisches Mittel zweier Zahlen · Eindeutigkeit der Methode der kleinsten Fehlerquadrate
- Wahrscheinlichkeitstheorie: Bernstein-Ungleichung · Satz von Moivre-Laplace · Approximationssatz von Stone-Weierstrass
- Kombinatorik: Kombinatorische Eigenschaft des Binomialkoeffizienten
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:
![{\displaystyle {\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant {\sqrt {\frac {2\sigma ^{2}{\mathcal {T}}}{n}}}+{\frac {2B{\mathcal {T}}}{3n}}\right]\leqslant e^{-{\mathcal {T}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef86ef376ce9ec687d6c4cb974fca29c364154a3)
Für den Beweis benötigt man folgendes
Für alle
gilt:

Man definiere die Linke Seite der Ungleichung als
, die rechte Seite als
und leite jeweils zweimal ab.






Es gilt:
Für
gilt:


Für
gilt:

Das gilt auch analog für
mit vertauschten Integralgrenzen.
Damit ist das Lemma gezeigt.
Der Beweis wird in fünf Schritte unterteilt:
Es wird zunächst gezeigt:

Allgemein gilt für
,
:
Zieht man auf beiden Seiten die Wurzel, dann folgt:
Mit
und
folgt die Ungleichung. Zur Vereinfachung wird die rechte Seite durch
definiert.

Zu zeigen:
Da die Zufallsvariablen nach Voraussetzung unabhängig sind, können Produkt und Erwartungswert vertauscht werden. Aus der Exponentialfunktion bilde man eine Exponentialreihe. Da
eine Integrierbare Majorante der unendlichen Reihe ist, können Erwartungswert und Summe vertauscht werden. Mit
und der Voraussetzung
folgt:

Zu zeigen:
Sei
die Verteilungsfunktion von
.
Nach Voraussetzung gilt:
für
bzw.
für 
für alle
und 


Diese Faktoren sind unabhängig von
. Mit
erhält man:

Aus
folgt, falls
positiv ist
und man erhält mit

Damit ist Schritt 3 gezeigt.
Zu zeigen:
Man setze
. Um das Lemma (oben) anzuwenden, setze man dann
.

Man setze
wie in Schritt 1 definiert ein:

Zum Schluss wird die Behauptung des Satzes gezeigt. Man wende zunächst Schritt 1 an.:
![{\displaystyle {\begin{aligned}{\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant {\sqrt {\frac {2\sigma ^{2}{\mathcal {T}}}{n}}}+{\frac {2B{\mathcal {T}}}{3n}}\right]&\leqslant {\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant {\frac {{\sqrt {18{\mathcal {T}}n\sigma ^{2}+{\mathcal {T}}^{2}B^{2}}}+{\mathcal {T}}B}{3n}}\right]\\&={\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant \epsilon \right]\\&={\textrm {P}}\left[t\sum _{i=1}^{n}X_{i}\geqslant t\epsilon n\right]\\&={\textrm {P}}\left[\exp \left(t\sum _{i=1}^{n}X_{i}\right)\geqslant \exp \left(t\epsilon n\right)\right]\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ece9d5f40b386269d58d735874f1457cd936d58e)
Nun wende man die Markow-Ungleichung an:
![{\displaystyle {\textrm {P}}\left[\exp \left(t\sum _{i=1}^{n}X_{i}\right)\geqslant \exp \left(t\epsilon n\right)\right]\leqslant \exp(-t\epsilon n){\textrm {E}}\left(\prod _{i=1}^{n}\exp(tX_{i})\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbf3f62ba9b8aa2d23c925a37da0c06c8e0f0df1)
Aus den Schritten 2 bis 4 folgt:

![{\displaystyle \Rightarrow {\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant {\sqrt {\frac {2\sigma ^{2}{\mathcal {T}}}{n}}}+{\frac {2B{\mathcal {T}}}{3n}}\right]\leqslant e^{-{\mathcal {T}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35c124b2064883372ad0374e6f745c4a335b57b4)