Theorem (Markovs Ungleichung) Sei $X$ eine Zufallsvariable, die nur nicht-negative Werte. Sei $c \gt 0$. Dann gilt
\begin{align*} \Pr[X \geq c] \leq \frac{\E[X]}{c} \ . \end{align*}Beispiel. Laut Wikipdia bzw. dem zitierten Global Wealth Report 2021 der Credit Suisse liegt das Durchschnittsvermögen von Erwachsenen in Deutschland bei 268.681 Euro. Was kann man allein aus diesem Wert schließen über die Anzahl der Vermögensmillionäre in Deutschland?
Rechnung. Unser Wahrscheinlichkeitsraum ist die Menge aller Erwachsenen in Deutschland; als Verteilung nehmen wir die Gleichverteilung. Die Zufallsvariable $X$ ist das Vermögen, $X(\omega)$ ist das Vermögen von $\omega$ in Euro, wobei $\omega$ ein Erwachsener in Deutschland ist. Laut Global Wealth Report 2021 gilt nun
\begin{align*} \E[X] = 268.681 \end{align*}Der Wert $c$ ist in unserem Beispiel 1.000.000. Mit Markovs Ungleichung schließen wir nun, dass
\begin{align*} \Pr[X \geq c] \leq \frac{\E[X]}{c} = \frac{268.681}{1.000.000} \approx 0.27 \ . \end{align*}Laut dem Statistischen Bundesamt gab es im Jahre 2020 circa 69.434.450 Erwachsene Personen in Deutschland. Die Anzahl der Vermögensmillionäre ist mit Markovs Ungleichung also höchstens
\begin{align*} 18.608.432 \end{align*}Das ist natürlich unrealistisch hoch. Dennoch "theoretisch" möglich: wenn man beliebige 18.608.432 Erwachsene auswählt und das Gesamtvermögen aller Personen in Deutschland gleich auf diese verteilte (während der Rest leer ausgeht), so hätte man über 18 Millionen Einkommensmillionäre geschaffen.
Beispiel: Roulette. Ein Roulette-Scheibe hat 37 Zahlen: $0, 1, \dots 36$. Davon sind 18 rot, 18 schwarz und eine grün (die 0). Ein Spieler startet mit einem Jeton. In jeder Runde setzt er einen Jeton auf rot; die Kugel fällt mit Wahrscheinlichkeit
\begin{align*} p := \frac{18}{37} \end{align*}auf rot, und der Spieler gewinnt. In diesem Falle bekommt er zwei Jetons, sein Vorrat ist also um 1 gewachsen. Mit Wahrscheinlichkeit $1-p$ verliert er, und sein Vorrat an Jetons schrumpft. Hat er keine Jetons mehr, hört er auf zu verlieren.
Sei $X$ die Anzahl der Runden, die der Spieler spielt (Vorsicht: dies kann rein theoretisch unendlich sein - wir haben es hier nicht mehr mit einem endlichen Wahrscheinlichkeitsraum zu tun). Was ist $\mu := \E[X]$?
Stellen wir eine allgemeinere Frage: sei $X^{(t)}$ die Anzahl der Schritte, die der Spieler spielen wird, wenn er mit $t$ Jetons beginnt. Da er im Schnitt $\mu$ Runden braucht, um von $1$ Jeton auf $0$ Jetons zu kommen, braucht er auch $\mu$ Runden, um von $t$ auf $t-1$ Jetons zu kommen (das wird klar, wenn Sie sich vorstellen, dass er $t-1$ Jetons in seiner Hosentasche verwahrt und nur mit einem auf dem Tisch beginnt). Nochmals im Erwartungswert $\mu$ Schritte braucht er von $t-1$ nach $t-2$, und so weiter, und somit gilt
\begin{align*} \E[X^{(t)}] = t \cdot \mu \ . \end{align*}Wenn wir nun mit einem Jeton starten, dann landen wir mit Wahrscheinlichkeit $1-p$ bei $0$ und die Anzahl der weiteren Runden ist $0$; mit Wahrscheinlichkeit $p$ landen wir bei $2$ Jetons; die Anzahl weiterer Runden ist nun verteilt wie $X^{(2)}$, und somit gilt
\begin{align*} \mu = \E[X] = 1 + p \cdot \E\left[X^{(2)}\right] = 1 + 2 p \mu \ , \end{align*}und somit
\begin{align*} \mu = \frac{1}{1 - 2p} \ . \end{align*}In unserem Beispiel ist $p = \frac{18}{37}$ und somit ist
\begin{align*} \mu = \frac{1}{1- 2p} = \frac{1}{1 - \frac{36}{37}} = \frac{37}{37 - 36} = 37 \ . \end{align*}Siebenunddreißig Runden spielt unser Freund im Schnitt, bis er keine Jetons mehr hat.
Was ist nun die Wahrscheinlichkeit, dass unser Spieler mehr als 1000 Runden durchhält? Das wäre höchstens
\begin{align*} \Pr[X \geq 1000] \leq \frac{\E[X]}{1000} = \frac{37}{1000} \ . \end{align*}Auch hier ist die Realität deutlich kleiner als was Markovs Ungleichung uns gibt, wie wir später sehen werden.
Varianz und die Tschebyschoff-Ungleichung
Der Erwartungswert gibt an, welchen Wert die Zufallsvariable $X$ "im Durchschnitt" annimmt. Die Varianz misst nun, wie sehr sie im Schnitt von diesem Mittelwert abweicht.
Definition (Varianz). Sei $X$ eine Zufallsvariable und $\mu := \E[X]$ ihr Erwartungswert. Dann ist
\begin{align*} \Var(X) := \E\left[ (X - \mu)^2 \right] \end{align*}die Varianz von $X$.
Hätten wir, um die durchschnittliche Abweichung vom Mittelwert zu messen, nicht eher $\E[X- \mu]$ definieren sollen? Nun, das wäre sinnlos: $\E[X-\mu] = \E[X] - \mu = 0$, die mittlere Abweichung (mit Vorzeichen!) ist $0$. Gut, aber würde $\E[ |X - \mu|]$ nicht mehr Sinn ergeben? Vielleicht, doch es stellt sich heraus, dass sich mit $(X-\mu)^2$ viel schöner rechnen lässt als mit $|X - \mu|$.
Theorem (Tschebyschoff-Ungleichung). Sei $X$ eine Zufallsvariable, $\mu = \E[X]$ und sei $c \gt 0$. Dann gilt
\begin{align*} \Pr[ |X - \mu| \geq c] \leq \frac{\Var(X)}{c^2} \ . \end{align*}Beweis. Wir setzen $Z := (X-\mu)^2$. Dies ist eine nicht-negative Zufallsvariable, daher können wir die Markov-Ungleichung anwenden:
\begin{align*} \Pr[ |X - \mu| \geq c] & = \Pr\left[ \left(X - \mu\right)^2 \geq c^2\right] \\ & = \Pr[Z \geq c^2] \\ & \leq \frac{\E[Z]}{c^2} \\ & = \frac{\Var(Z)}{c^2} \ . \end{align*} \(\square\)Durch das $c^2$ im Nenner können wir mit der Tschebyschoff-Ungleichung deutlich schärfere Schranken beweisen als mit Markov - falls $\Var(X)$ klein sein. Auch können wir Abweichungen nach unten, also $\Pr[ X \leq \mu - c]$ beschränken, was mit Markovs Ungleichung alleine völlig unmöglich ist. Um die Tschebyschoff-Ungleichung sinnvoll anwenden zu können, müssen wir also Techniken lernen, wie man die Varianz von Zufallsvariablen berechnet bzw. erreicht, dass diese klein ist.
Lemma (Eine alternative Formel für die Varianz). Sei $X$ eine Zufallsvariable mit $\mu := \E[X]$. Es gilt
\begin{align*} \Var(X) = \E\left[X^2\right] - \mu^2 \ . \end{align*}Beweis. Wir rechnen:
\begin{align*} \Var(X) & = \E\left[\left(X - \mu\right)^2 \right] \\ & =\E\left[X^2 - 2 X \mu + \mu^2\right] = \E\left[X^2\right] - 2 \mu \E[X] + \mu^2 \\ & = \E\left[X^2\right] - 2 \mu \cdot \mu + \mu^2 \\ & = \E\left[X^2\right] - \mu^2 \\ \end{align*} \(\square\)Lemma Seien $X_1, \dots, X_k$ paarweise unabhängige Zufallsvariable. Dann gilt
\begin{align*} \Var(X_1 + \cdots + X_k) & = \Var(X_1) + \cdots + \Var(X_k) \ . \end{align*}Beweis. Sei $X := X_1 + \cdots + X_k$ und $\mu_i := \E[X_i]$ und $\mu = \E[X]$. Wir rechnen
\begin{align*} \E\left[X^2\right] & = \E\left[\left(\sum_{i=1}^k X_i\right)^2\right] \\ & = \E\left[\sum_{i=1}^k \sum_{j=1}^k X_i X_j \right] \\ & = \sum_{i=1}^k \sum_{j=1}^k \E[X_i \cdot X_j] \ . \end{align*}Was ist $\E[X_i \cdot X_j]$? Wenn $i \ne j$ ist, dann sind $X_i, X_j$ unabhängig und es gilt $\E[X_i \cdot X_j] = \mu_i \cdot \mu_j$. Wenn $i = j$ ist, dann ist $\E[X_i \cdot X_j] = \E\left[X_i^2\right] = \Var(X_i) + \mu_i^2$. Wir teilen also obige Summe auf in $i \ne j$ und $i=j$:
\begin{align*} \E\left[X^2\right] & = \sum_{i=1}^k \sum_{j=1}^k \E[X_i \cdot X_j] \\ & = \sum_{i=1}^k \sum_{j=1}^k [i \ne j] \mu_i \cdot \mu_j + \sum_{i=1}^k \left( \Var(X_i) + \mu_i^2 \right) \end{align*}Jetzt fügen wir die Terme $\mu_i \cdot \mu_j$ für $i = j$ der ersten Summe hinzu, müssen sie jedoch gleich wieder abziehen, damit Gleichheit garantiert ist:
\begin{align*} \E\left[X^2\right] & =\sum_{i=1}^k \sum_{j=1}^k [i \ne j] \mu_i \cdot \mu_j + \sum_{i=1}^k \left( \Var(X_i) + \mu_i^2 \right) \\ & = \sum_{i=1}^k \sum_{j=1}^k \mu_i \cdot \mu_j - \sum_{i=1}^k \mu_i^2 + \sum_{i=1}^k \left( \Var(X_i) + \mu_i^2 \right) \\ & = \sum_{i=1}^k \sum_{j=1}^k \mu_i \cdot \mu_j + \sum_{i=1}^k \Var(X_i) \\ & = \left(\sum_{i=1}^k \mu_i\right)^2 + \sum_{i=1}^k \Var(X_i) \\ & = \mu^2 + \sum_{i=1}^k \Var(X_i) \ . \end{align*}und somit gilt
\begin{align*} \Var(X) & = \E\left[X^2\right] - \mu^2 = \sum_{i=1}^k \Var(X_i) \ , \end{align*}wie behauptet. \(\square\)
Beachten Sie, dass wir für nicht volle sondern nur paarweise Unabhängigkeit benötigen.
Beispiel: Wohnung saugen. Ihr Mitbewohner bzw. Ihre Mitbewohnerin und Sie haben eine Abmachung. Um sich Strichlisten zu ersparen, werfen Sie einmal pro Woche eine Münze: Kopf und Sie saugen Staub; Zahl und Ihr Mitbewohner saugt Staub. Wie oft müssen Sie in den 52 Wochen des Jahres voraussichtlich Staub saugen? Im Schnitt 26 mal. Wie hoch ist das Risiko, dass es sehr ungerecht ausgeht, dass Sie also 35 mal oder mehr Staub saugen müssen?
\begin{align*} X_i := \begin{cases} 1 & \textnormal{ wenn Sie in Woche $i$ Staub saugen müssen} \\ 0 & \textnormal{ andernfalls.} \end{cases} \end{align*}Sie müssen in diesem Jahr also $X := \sum_{i=1}^{5} X_i$ mal Staub saugen. Es gilt
\begin{align*} \E[X] & = \sum_{i=1}^{52} \E[X_i] = 26 \ . \end{align*}Nach Markov gilt also
\begin{align*} \Pr[X \geq 35] \leq \frac{\E[X]}{35} = \frac{26}{35} \ , \end{align*}was durchaus ein nicht zu vernachlässigendes Risiko ist. Berechnen wir nun die Varianz:
\begin{align*} \Var(X) = \sum_{i=1}^{52} \Var(X_i) \tag{weil unabhängig} \ . \end{align*}Was ist $\Var(X_i)$?
\begin{align*} \Var(X_i) = \E[\left(X_i\right)^2] - \left(\E\left[X_i\right]\right)^2 \ . \end{align*}Da $X_i$ nur die Werte $0$ und $1$ annehmen kann, gilt $X_i^2 = X_i$ und somit
\begin{align*} \Var(X_i) & = \E[\left(X_i\right)^2] - \left(\E\left[X_i\right]\right)^2 \\ & = \E\left[X_i\right] - \left(\E\left[X_i\right]\right)^2 \\ & = \frac{1}{2} - \frac{1}{4} = \frac{1}{4} \ \end{align*}und somit $\Var(X) = \frac{52}{4} = 13$.