Kartenhausverteilung

Wie oft muss ich im Durchschnitt eine Münze werfen, um 4 mal in Folge Zahl zu haben? Diese Fragestellung versuchen wir in diesem Artikel zu klären.
Anschaulich können wir dies auch mit einem Kartenhaus erklären. Wir wollen eine Höhe von 4 Stockwerken haben. Fällt im dritten Schritt das Haus zusammen, so müssen wir wieder von vorne beginnen. Im besten Fall benötigen wir 4 Schritte. Im schlimmsten Fall schaffen wir es nie.

Versuchen wir dieses Zufallsexperiment etwas mathematischer zu beleuchten. Hierfür benötigen wir einige Variablen und Größen, die wir kurz durch gehen.

• $x$ ist die gewünschte Anzahl an Erfolgen in Reihe. Bei uns ist $x=4$.
• $N_x$ ist unsere Zufallsvariable, die die Anzahl der Versuche zählt, bis wir $x$ Erfolge in Reihe haben.
• $p$ ist die Wahrscheinlichkeit im nächsten Schritt einen Erfolg zu erzielen.

Im Falle des Münzwurfes ist $p=0{,}5$.

Die einfachste Möglichkeit die Frage vom Beginn zu klären, ist es den Erwartungswert der Zufallsgröße $N_x$ zu bestimmen. Hierfür benötigen wir aber die Verteilung von $N_x$. Alternativ kann man auch mittels einiger Simulationen versuchen, die Verteilung zu approximieren und dann den Erwartungswert zu bestimmen.

Nichts Einfacheres als das. Wir brauchen nur eine Münze und viel, wirklich viel Zeit. Na dann mal los. Ein Klick auf den Button startet einen Versuch. Diesen kannst du natürlich beliebig oft wiederholen.

Versuch starten



Natürlich reicht ein Versuch nicht aus. Ich habe 10.000 mal dieses Experiment durchgeführt. Natürlich habe ich keine Münze geworfen. Ein wenig Code und PC-Unterstützung haben ausgereicht. Der schlechteste Versuch brauchte 315 Würfe, um 4 mal in Folge Zahl zu erreichen. Der Durchschnitt lag bei 29,95336 Versuchen. Wenn man schon einmal beim programmieren ist, kann man auch andere Szenarien testen. Ich habe also auch die Fälle $x=1$, $x=2$, $x=3$ und $x=5$ ebenfalls getestet. Jedes mal wurde der Versuch 10.000 mal wiederholt. Die Durchschnittswerte bis zum x-ten Erfolg in Folge sind in folgender Tabelle aufgelistet.

$x$	durchschnittliche Anzahl an Versuchen
$1$	$2$
$2$	$6$
$3$	$14$
$4$	$30$
$5$	$62$

Gibt es eine Logik die hinter der rechten Spalte steckt? Wer gerne Zahlenreihen löst, dem fällt vielleicht etwas auf. Wenn du magst dann nimm dir einen Augenblick, bevor es im nächsten Abschnitt weiter geht.

Was fällt einem auf? Wir addieren beim ersten mal 4, danach 8, danach 16, danach 32. Als nächstes würde man $2\cdot32=64$ addieren. Wir würden also bei 126 landen.
Alternativ kann man auch folgende Logik unterstellen: Wir landen immer 2 unterhalb einer Potenz von 2.

$x$	durchschnittliche Anzahl an Versuchen
$1$	$2 = 4-2 = 2^2-2$
$2$	$6 = 8-2 = 2^3-2$
$3$	$14 = 16-2 = 2^4-2$
$4$	$30 = 32-2 = 2^5-2$
$5$	$62 = 64 - 2 = 2^6-2$

Wir haben bisher nur ein paar Simulationen gemacht, aber dadurch eine Vermutung über die Entwicklung bekommen. Solche Experimente sind sehr wichtig. Da man so eine Idee entwickeln kann, die man dann nur noch beweisen muss.

Im Folgenden wollen wir unsere obige Vermutung beweisen und dies sofort etwas allgemeiner. Wir werden die Wahrscheinlichkeit $p$ variabel lassen.

Wir setzen zur Veranschaulichung $x=2$. Nun könnten die folgenden drei Fälle auftreten:

1. Wir haben zwei mal in Folge Erfolg.
2. Wir haben erst Erfolg und dann Misserfolg.
3. Wir haben sofort Misserfolg.

Wie sehen nun die einzelnen Wahrscheinlichkeiten für diese drei Fälle aus? Schauen wir uns hierzu ein Baumdiagramm an:

Wenn wir uns nun dem Erwartungswert nähern, so lassen sich für die drei Fälle die folgenden Aussagen formulieren:

1. Nach zwei Schritten ist man am Ziel.
2. Wir haben zwei Schritte gemacht und müssen wieder von vorne starten.
3. Wir haben einen Schritte gemacht und müssen wieder von vorne starten.

Da wir in den Fällen zwei und drei wieder von vorne starten müssen erhöt sich die Weite in diesem Fällen um 2 beziehungsweise 1.

1. Schrittweite: $2$
2. Schrittweite: $2 + \mathbb{E}(N_x)$
3. Schrittweite: $1 + \mathbb{E}(N_x)$

Diese drei Punkte ergeben nun im Kombination mit ihren Wahrscheinlichkeiten (siehe oben) den gesuchten Erwartungswert. \begin{align} \mathbb{E}(N_2) &= p^2 \cdot 2 + p \cdot (1-p) \cdot \left(1 + 1 + \mathbb{E}(N_2) \right) + (1-p) \cdot \left( 1 + \mathbb{E}(N_2) \right) \\ &= 2p^2 + \left(p - p^2\right) \cdot \left(2 + \mathbb{E}(N_2) \right) + (1-p) \cdot \left( 1 + \mathbb{E}(N_2) \right) \\ &= 2p^2 + 2p + p\cdot \mathbb{E}(N_2) - 2p^2 - p^2 \cdot \mathbb{E}(N_2) + 1 + \mathbb{E}(N_2) - p - p \cdot \mathbb{E}(N_2) \\ &= p + \mathbb{E}(N_2) \cdot \left( p - p^2 + 1 - p\right) + 1 \end{align} Nun haben wir auf beiden Seiten $\mathbb{E}(N_2)$ stehen. Wir können also nach dem Erwartugnswert auflösen indem wir ihn auf eine Seite bringen und durch den Vorfaktor teilen. Gesagt getan. \begin{align} \mathbb{E}(N_2) &= p + \mathbb{E}(N_2) \cdot \left( p - p^2 + 1 - p\right) + 1 &&|-\mathbb{E}(N_2) \cdot \left( p - p^2 + 1 - p\right)\\ \mathbb{E}(N_2) \cdot \left( 1 - p + p^2 - 1 + p\right) &= p + 1 && \\ \mathbb{E}(N_2) \cdot p^2 &= p + 1 &&|:p^2 \\ \mathbb{E}(N_2) &= \frac{p + 1}{p^2} && \end{align} Nun brauchen wir nur noch unsere Wahrscheinlichkeit $p=0{,}5$ einsetzen und erhalten: \begin{align} \mathbb{E}(N_2) &= \frac{0{,}5 + 1}{0{,}5^2} \\ \mathbb{E}(N_2) &= \frac{1{,}5}{0{,}25} \\ \mathbb{E}(N_2) &= 6 \end{align} Diesen Erwartungswert kennen wir schon von oben aus der Tabelle.

Neben der Wahrscheinlichkeit $p$ können wir ebenfalls die Anzahl der notwendigen Erfolge $x$ variabel lassen. Den Beweis hierfür würde ich nur kurz einleiten.

Wir schon im Fall $x=2$ schauen wir uns an, wie man zum Erfolg kommt.

1. Nach $x$ Schritten ist man am Ziel.
2. Wir haben $x-1$ Schritte gemacht und müssen wieder von vorne starten.
3. Wir haben $x-2$ Schritte gemacht und müssen wieder von vorne starten.
4. $\ldots$
5. Wir haben einen Schritte gemacht und müssen wieder von vorne starten.

Mit dieser Logik können wir wieder den Erwartungswert bestimmen wie gerade. \begin{align} \mathbb{E}(N_x) &= p^x \cdot x + \sum_{k=0}^{x-1} p^k \cdot (1-p) \cdot \left(k + 1 + \mathbb{E}(N_x) \right) \\ &= p^x \cdot x + \sum_{k=0}^{x-1} p^k \cdot (1-p) \cdot k + \sum_{k=0}^{x-1} p^k \cdot (1-p) \cdot \left( 1 + \mathbb{E}(N_x) \right) \\ &= p^x \cdot x + (1-p) \cdot \sum_{k=0}^{x-1} p^k \cdot k + (1-p) \cdot \left( 1 + \mathbb{E}(N_x) \right) \cdot \sum_{k=0}^{x-1} p^k \end{align} An dieser Stelle helfen uns zwei Partialsummen weiter: Mit diesen beiden Partialsummen können wir unsere obige Formel für den Erwartungswert weiter ausrechnen.
Nach zahlreichen Zeilen umformen und vereinfachen erhalten wir die folge Lösung für den Erwartungswert. Für $p=0{,}5$ erhalten wir die obige Formel.