Spezielle Wahrscheinlichkeitsverteilungen: Lösung von Wartezeitproblemen mit Hilfe der geometrischen Verteilung

Einordnung des Artikels

• Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
  • Wahrscheinlichkeitsrechnung
    • Grundbegriffe der Wahrscheinlichkeitsrechnung
      • Grundbegriffe der Wahrscheinlichkeitsrechnung: Binomialkoeffizienten, das Pascalsche Dreieck und der n-dimensionale Hyperwürfel
      • Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars
    • Eigenschaften von Zufallsvariablen
      • Berechnung von Erwartungswerten und Varianzen mit Hilfe von Indikatorvariablen
    • Spezielle Wahrscheinlichkeitsverteilungen
      • Spezielle Wahrscheinlichkeitsverteilungen: die geometrische Verteilung

Einführung

In Spezielle Wahrscheinlichkeitsverteilungen: die geometrische Verteilung wurde der Zusammenhang zwischen dem Münzwurf und der geometrischen Verteilung diskutiert: Wirft man eine Münze (mit Trefferwahrscheinlichkeit p) so lange bis der erste Treffer eintritt, gehorcht die Anzahl der nötigen Würfe der geometrischen Verteilung.

Es ist naheliegend dieses Wartezeitproblem zu verallgemeinern: Man wirft die Münze so lange bis der r-te Treffer eintritt. Untersucht wird dann die Zufallsvariable X_r,p, die die Anzahl der Würfe beschreibt, wobei r = 1, 2, ...

Im Folgenden werden die Verteilung der Zufallsvariable X_r,p hergeleitet, ihre Eigenschaften untersucht (wie Erwartungswert, Standardabweichung) sowie einfache Beispiele diskutiert.

Die geometrische Verteilung als Verteilung von Wartezeiten

In Spezielle Wahrscheinlichkeitsverteilungen: die geometrische Verteilung wurde die geometrische Verteilung diskutiert. Dabei wurde gezeigt, dass man sie als die Verteilung einer Wartezeit interpretieren kann. Damit ist gemeint:

• Ein Zufallsexperiment mit zwei möglichen Ausgängen (Treffer und Niete) wird unabhängig voneinander wiederholt. Bei dem Zufallsexperiment kann es sich zum Beispiel um einen Münzwurf handeln, relevant ist hier lediglich, dass es zwei Elementarereignisse gibt.
• Die Wahrscheinlichkeit für einen Treffer werde mit p bezeichnet, die Wahrscheinlichkeit für eine Niete mit q = 1 - p.
• Das Zufallsexperiment wird solange wiederholt bis der erste Treffer eintritt.
• Gesucht sind jetzt die Wahrscheinlichkeiten dafür, dass der erste Treffer nach i Wiederholungen des Experimentes eintritt.
• Definiert man die Zufallsvariable X als die Anzahl der Wiederholungen i bis zum ersten Treffer, so sind die Wahrscheinlichkeiten gesucht:

P(X = i), i = 1, 2, ...

Im Folgenden wird angenommen, dass es sich bei dem Zufallsexperiment um einen Münzwurf handelt, der unabhängig voneinander wiederholt wird. Die Trefferwahrscheinlichkeit der Münze betrage p.

In Abbildung 1 wird versucht dieses Wartezeitproblem mit Hilfe eines Baumdiagramms darzustellen:

• Treffer sind jeweils die Zweige nach links, Nieten die Zweige nach rechts (blau).
• Das Experiment wird beendet, wenn ein Treffer eintritt (roter Zweig).
• Wertet man das Baumdiagramm aus, erhält für die gesuchten Wahrscheinlichkeiten:

P(X = i) = pq^i-1, i = 1, 2, ...

Die Zufallsvariable X ist somit geometrisch verteilt mit Parameter p.

Abbildung 1: Darstellung des Wartezeitproblems in einem Baumdiagramm: Jede Verzweigung steht für einen Münzwurf (Treffer 1 nach links, Nieten 0 nach rechts). Das Zufallsexperiment wird beendet sobald der erste Treffer eintritt. Die Auswertung des Baumdiagramms liefert die Wahrscheinlichkeiten der Wartezeiten P(X = i) = pq^i-1, i = 1, 2, ...: sie stimmen mit einer geometrischen Verteilung mit Parameter p überein.

Die Fragestellung nach der Wartezeit bis zum ersten Treffer kann jetzt leicht verallgemeinert werden: Das Zufallsexperiment wird so lange durchgeführt bis r Treffer eintreten (mit r = 1, 2, ...). Im Folgenden wird dieses verallgemeinerte Wartezeitproblem untersucht. Man könnte sogar noch einen Schritt weitergehen und die geometrische Verteilung als Spezialfall einer allgemeineren Klasse von Verteilungen auffassen.

Verallgemeinerung: Eine spezielle Klasse von Wartezeitproblemen

Eine naheliegende Verallgemeinerung des oben formulierten Wartezeitproblems lautet:

Es wird eine ganze Zahl r = 1, 2, ... vorgegeben; das Zufallsexperiment von oben (Münzwurf mit Trefferwahrscheinlichkeit p) wird so lange wiederholt, bis der r-te Treffer eingetreten ist.

Anstelle der Zufallsvariable X von oben definiert man jetzt die Zufallsvariable X_r,p, die angibt nach wie vielen Würfen i der Münze der r-te Treffer eintritt. Gesucht sind dann die Wahrscheinlichkeiten

P(X_r,p = i) , i = r, r+1, r+2, ...

Die Indizes in X_r,p geben die Anzahl der Treffer r und die Trefferwahrscheinlichkeit p an. Falls aus dem Zusammenhang erkennbar ist, welche Parameter gewählt wurden, wird anstelle von X_r,p wieder X geschrieben.

Für i < r sind die Wahrscheinlichkeiten natürlich gleich null. Und für r = 1 erhält man die geometrische Verteilung.

In Abbildung 2 wird das zu Abbildung 1 analoge Baumdiagramm dargestellt, wobei r = 2 gewählt ist.

Abbildung 2: Baumdiagramm zur Lösung des Wartezeitproblems: mit welcher Wahrscheinlichkeit tritt nach i Würfen der Münze der zweite Treffer ein? Zweige nach rechts (Nieten) sind blau dargestellt, Zweige nach links dunkelrot für den ersten Treffer und rot für den zweiten Treffer; nach dem zweiten Treffer bricht das Zufallsexperiment ab.

Das Baumdiagramm beschreibt zwar den Spezialfall r = 2, aber man kann die dort gezeigte Überlegung verwenden, um die Wahrscheinlichkeiten P(X_r,p = i) für das Wartezeitproblem zu berechnen. Im folgenden Abschnitt wird die Lösungsansatz diskutiert und die Wahrscheinlichkeiten P(X_r,p = i) berechnet.

Lösung des Wartezeitproblems

Mit Hilfe von Abbildung 2 soll nun das im letzten Unterabschnitt formulierte Wartezeitproblem gelöst werden, sprich es sollen zu gegebenen r und p die folgenden Wahrscheinlichkeiten berechnet werden:

P(X_r,p = i) , i = r, r+1, r+2, ...

Das Ereignis X_r,p = i bedeutet ausführlich beschrieben:

1. Es werden i Münzwürfe durchgeführt (jeweils mit Trefferwahrscheinlichkeit p).
2. Insgesamt treten r Treffer ein.
3. Der letzte (also der r-te) Treffer tritt beim i-ten Experiment ein. (In Abbildung 2 ist der Spezialfall zu r = 2 gezeigt: nach dem zweiten Treffer bricht das Zufallsexperiment ab.)

Aus den letzten beiden Bedingungen folgt aber, dass bei den ersten i-1 Münzwürfen genau r-1 Treffer eintreten, wobei ihre Reihenfolge beliebig sein kann. Lediglich das Ergebnis des letzten Münzwurfs ist festgelegt: der i-te Münzwurf ist ein Treffer.

Man kann dies gut in Abbildung 2 rechts nachverfolgen; dazu werden die Ergebnisse des Zufallsexperimentes als Dualzahl geschrieben:

1. Die letzte Stelle muss eine 1 sein (Treffer).
2. Die Länge der Dualzahl beträgt i.
3. In der ersten i-1 Stellen der Dualzahl enthalten r-1 Treffer.

Da die Münzwürfe unabhängig voneinander sind, kann man jetzt die Wahrscheinlichkeiten P(X_r,p = i) berechnen:

• Die Anzahl der möglichen Folgen mit r Treffern und i-r Nieten wird durch den Binomialkoeffizienten "(r-1) aus (i-1)" beschrieben. Denn das letzte Ergebnis muss ein Treffer sein und die anderen r-1 Treffer können auf i-1 Stellen verteilt werden. Die Anzahl der möglichen Anordnung wird dann durch den Binomialkoeffizient berechnet (siehe Gleichung (1) in Abbildung 3)
• Es treten r Treffer und i - r Nieten ein. Daher ist die Wahrscheinlichkeit einer beliebigen Anordnung der Treffer und Nieten gleich: p^r·q^i-r (siehe Gleichung (2) in Abbildung 3). Hier wird verwendet, dass die Trefferwahrscheinlichkeit p für jeden Münzwurf identisch ist.

Insgesamt erhält man daraus die Wahrscheinlichkeit P(X_r,p = i) gemäß Gleichung (3) in Abbildung 3.

Abbildung 3: Lösung des allgemeinen Wartezeitproblems durch Abzählen der möglichen Anordnungen und Berechnen der Wahrscheinlichkeit einer Anordnung.

Da auf jeden Fall r Münzwürfe durchgeführt werden müssen, ist es naheliegend nicht die Zufallsvariable X_r,p zu betrachten, sondern zu zählen wie viele Münzwürfe nach dem r-ten Wurf durchgeführt werden. Dies beschreibt die Zufallsvariable

Y_r,p = X_r,p - k , k = 0, 1, 2, ...

Die Wahrscheinlichkeiten

P(Y_r,p = k) , k = 0, 1, 2, ...

können leicht auf diejenigen von P(X_r,p = i) zurückgeführt werden, indem man k = i - r setzt, siehe Gleichung (4) in Abbildung 3. Wegen der Symmetrie des Binomialkoeffizienten, kann man diese Wahrscheinlichkeiten auch nach Gleichung (5) berechnen.

Aufgaben:

1. In (6) und (7) in Abbildung 3 wird die Bedeutung des Terms p^r·q^k sowie des Binomialkoeffizienten kurz beschrieben. Geben Sie eine ausführliche Herleitung der Wahrscheinlichkeiten P(Y_r,p = k) , k = 0, 1, 2, ... mit einer ähnlichen Überlegung wie oben.

2. Der Binomialkoeffizient in Gleichung (5) beziehungsweise (7) stimmt mit dem Binomialkoeffizienten überein, der mit der Beweismethode Stars and Bars diskutiert wurde (siehe Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars). Diskutieren Sie: Handelt es sich hier um eine zufällige Übereinstimmung oder kann man das Abzählen der Ergebnisse der Münzwürfe mit der Methode Stars and Bars durchführen?

Berechnung des Erwartungswertes, der Varianz und der Standardabweichung der Wartezeiten

In Gleichung (3) in Abbildung 3 wurde die Verteilung der Wartezeiten angegeben, wenn eine Münze mit Trefferwahrscheinlichkeit p verwendet wird und so lange geworfen wird bis der r-te Treffer eintritt. Diese Anzahl von Treffern wird durch die Zufallsvariable X_r,p beschrieben, die die Werte r, r+1, r+2, ... annehmen kann.

Es ist naheliegend zu fragen:

Wie groß ist der Erwartungswert der Zufallsvariable X_r,p?

Um diese Frage zu beantworten, gibt es zwei Ansätze:

1. Der naheliegende Ansatz ist es, Gleichung (3) in Abbildung 3 zu verwenden: Der Erwartungswert wird dann wie in Gleichung (2) in Abbildung 4 berechnet. Dieser Ansatz führt zu umständlichen Berechnungen, die unten kurz angedeutet werden.
2. Deutlich einfacher geschieht die Berechnung des Erwartungswertes, indem geeignete Zufallsvariablen eingeführt werden, deren Summe die Zufallsvariable X_r,p ergibt. Das Problem lässt sich dadurch auf die Berechnung des Erwartungswertes der geometrischen Verteilung zurückführen. (Siehe Gleichung (3) in Abbildung 4.)

Abbildung 4: Berechnung des Erwartungswertes, der Varianz und der Standardabweichung der Wartezeiten.

Direkte Berechnung des Erwartungswertes aus der Verteilung

In Spezielle Wahrscheinlichkeitsverteilungen: die geometrische Verteilung wurde ausführlich gezeigt, wie der Erwartungswert der geometrischen Verteilung berechnet wird: Die Summe, die dabei auftritt kann auf eine geometrische Reihe zurückgeführt werden. Dieser Ansatz ist auch für die Berechnung der Summe in Gleichung (2) in Abbildung 4 möglich - vergleicht man diese Berechnung allerdings mit dem zweiten Ansatz, so erkennt man, dass sie sehr umständlich und fehleranfällig ist.

Aufgabe: Berechnen Sie den Erwartungswert gemäß Gleichung (2) in Abbildung 4, indem Sie die Summe auf eine geometrische Reihe zurückführen. (Siehe dazu auch Abbildung 4 in Spezielle Wahrscheinlichkeitsverteilungen: die geometrische Verteilung.)

Zurückführen auf den Erwartungswert der geometrischen Verteilung

In Berechnung von Erwartungswerten und Varianzen mit Hilfe von Indikatorvariablen wurde eine Methode vorgestellt, die häufig angewendet werden kann: Gelingt es ein Zufallsvariable durch eine Summe von sehr einfachen Zufallsvariablen darzustellen, so ist wegen der Linearität des Erwartungswertes E(X + Y) = E(X) + E(Y) auch die Berechnung des Erwartungswertes sehr einfach. Der entscheidende Schritt besteht darin, die geeigneten Summanden zu finden, deren Erwartungswert leicht zu berechnen ist.

Dazu muss man sich nochmals vergegenwärtigen, nach welchen Regeln das Zufallsexperiment durchgeführt wird:

1. Es werden unabhängige Würfe eine Münze durchgeführt (Trefferwahrscheinlichkeit p).
2. Das Zufallsexperiment ist beendet, wenn genau r Treffer eingetreten sind.

Damit kann man aber das Zufallsexperiment in genau r Zufallsexperimente zerlegen:

1. Das erste Zufallsexperiment besteht darin, so lange die Münze zu werfen bis ein Treffer eintritt. Die Zufallsvariable, die die Anzahl der Würfe bis zum ersten Treffer beschreibt, wird mit Z_p,1 bezeichnet.
2. Das zweite Zufallsexperiment startet, wenn das Erste abgeschlossen wird. Jetzt wird gezählt, wie viele Würfe nötig sind bis der zweite Treffer eintritt. Diese Zufallsvariable wird mit Z_p,2 bezeichnet.
3. Und so weiter ...

Addiert man diese r Zufallsvariablen, erhält man natürlich die Gesamtzahl der Würfe bis zum r-ten Treffer, also gerade X_r,p. Somit gilt (siehe Gleichung (3) in Abbildung 4):

X_r,p = Z_p,1 + Z_p,2 + ... + Z_p,r.

Die Zufallsvariablen Z_p,1, Z_p,2, ..., Z_p,r sind jeweils geometrisch verteilt mit Parameter p. Dies gilt, da die Zählung der Treffer jeweils von Neuem beginnt und die Verteilung nicht von der "Vorgeschichte" abhängt. (Die Münzwürfe sind unabhängig voneinander und somit ist jedes Z_p,j unabhängig von den vorausgegangenen Ergebnissen und geometrisch verteilt wie Z_p,1.)

Dann stimmt aber der Erwartungswert von Z_p,j mit 1/p überein (siehe Gleichung (4) in Abbildung 4). Und der Erwartungswert von X_r,p ergibt sich zu r/p (siehe Gleichung (5) in Abbildung 4).

Berechnung der Varianz und der Standardabweichung der Wartezeiten

Die Linearität des Erwartungswertes bei einer Summe von Zufallsvariablen, also

E(X + Y) = E(X) + E(Y),

gilt für alle Zufallsvariablen - hier wird keine Unabhängigkeit oder Unkorreliertheit von X und Y vorausgesetzt. Die entsprechende Formel für die Varianz, also

Var(X + Y) = Var (X) + Var(Y),

gilt nur dann, wenn die Kovarianz von X und Y gleich 0 ist:

cov(X, Y) = 0.

Andernfalls gilt:

Var(X + Y) = Var (X) + Var(Y) + 2cov(X, Y).

Speziell für unabhängige Zufallsvariablen X und Y gilt: cov(X, Y) = 0.

Da die Zufallsvariablen Z_p,j, j = 1. 2, ..., r, unabhängig voneinander sind, kann die Varianz von X_r,p mit der Summe der Varianzen der Z_p,j berechnet werden, siehe Gleichung (8) in Abbildung 4. Dazu benötigt man lediglich die Varianz einer geometrisch verteilten Zufallsvariable mit Parameter p; diese berechnet sich durch Gleichung (7) in Abbildung 4.

Durch Bildung der Wurzel erhält man die Standardabweichung der Wartezeiten X_r,p, siehe Gleichung (8) in Abbildung 4. Erwartungswert und Varianz der Wartezeiten X_r,p wachsen proportional zu r, die Standardabweichung wächst proportional zur Wurzel aus r.

1. Beispiel: fairer Münzwurf

Um die oben durchgeführten Berechnungen zu veranschaulichen, wird zunächst das einfachste Zufallsexperiment betrachtet, das ein Wartezeitproblem im oben definierten Sinn ist:

Eine Laplace-Münze (Trefferwahrscheinlichkeit p = 1/2) wird so lange geworfen bis genau r Treffer eingetreten sind, r = 1, 2, ...

Die Zufallsvariable X_r,p mit p = 1/2 beschreibt wie oben die Anzahl der Würfe bis zum r-ten Treffer. Die Wahrscheinlichkeiten P(X_r,p = i), i = r, r+1, ... werden nach Gleichung (3) in Abbildung 3 berechnet.

Abbildung 5 zeigt für die Werte r = 1, 2, 3, 4 die zugehörigen Histogramme. Dabei sind zusätzlich eingetragen:

• der Erwartungswert von E(X_r,p) (als grüne durchgezogene Linie),
• sowie das Intervall von E(X_r,p) - σ bis E(X_r,p) - σ, wobei σ die Standardabweichung gemäß Gleichung (8) in Abbildung 4 ist (die Intervallgrenzen sind grün und gestrichelt).

Abbildung 5: Verteilung der Wartezeit für den fairen Münzwurf für r = 1, 2, 3, 4. Zusätzlich eingetragen sind jeweils Erwartungswert und Standardabweichung der Wartezeiten. Um die Histogramme untereinander vergleichen zu können, ist die Skalierung der Achsen in allen Diagrammen identisch.

Für r = 1 erhält man die geometrische Verteilung mit Parameter p = 1/2. Man erkennt in Abbildung 5 ihre typischen Eigenschaften:

• Die Wahrscheinlichkeiten dafür, dass i Würfe bis zum ersten Treffer ausgeführt werden, nehmen exponentiell mit i ab.
• Der Erwartungswert ist der Kehrwert von p, hier also gleich 2. Das heißt im Durchschnitt muss man zweimal die Münze werfen bis der erste Treffer eintritt.
• Die Standardabweichung stimmt mit der Wurzel aus 2 überein, ist also etwa gleich 1.41 (siehe Gleichung (8) in Abbildung 4 mit p = q = 1/2 und r = 1).

Für r = 2 kann man zum Verständnis des Histogramms entweder Abbildung 2 (Baumdiagramm) zu Hilfe nehmen oder direkt in Gleichung (3) in Abbildung 3 einsetzen (mit p = q = 1/2 und r = 2). In Abbildung 6 werden einige Berechnungen ausgeführt, die auf Gleichung (3) in Abbildung 3 zurückgreifen (die Verteilung der Wartezeiten ist nochmals in Gleichung (1) in Abbildung 6 gezeigt):

1. Die Berechnung der Wahrscheinlichkeit P(X_r,p = i) wird in zwei Anteile zerlegt, deren i-Abhängigkeit diskutiert wird: Einmal der Term p^r·q^r-i, der angibt wie groß die Wahrscheinlichkeit für eine Realisierung von r Treffern und r - i Nieten ist. Zum Anderen der Binomialkoeffizient, der angibt wie viele derartige Realisierungen es gibt.
2. Setzt man p = q = 1/2 und r = 2, so erkennt man: Der Term p^r·q^r-i fällt exponentiell mit i (geometrische Folge). Der Binomialkoeffizient wächst proportional mit i.
3. Insgesamt erhält man für P(X_r,p = i) Gleichung (2) in Abbildung 6.
4. Weiter sind in der Tabelle die Wahrscheinlichkeiten P(X_r,p = i) für i = 2, 3, 4, 5, 6 angegeben - zum besseren Vergleich sind sie in der letzten Zeile auf gleichen Nenner gebracht.
5. In Gleichung (3) in Abbildung 6 werden Erwartungswert und Standardabweichung berechnet (nach Gleichung (8) in Abbildung 4).

Mit diesen Berechnungen kann man leicht die Darstellung des Histogramms in Abbildung 5 nachvollziehen. Weiter erkennt man, dass der Erwartungswert proportional zu r zunimmt, wenn p konstant gehalten wird und r variiert

Für r = 3 werden obige Berechnungen nochmals durchgeführt. Der wesentliche Unterschied besteht jetzt darin, dass der Binomialkoeffizient quadratisch mit i anwächst. Dadurch wird verständlich, warum die Verteilung der Wartezeiten ein Maximum besitzt, das aber nicht eindeutig ist (bei i = 4 und i = 5, siehe Abbildung 5).

Abbildung 6: Ausführliche Berechnung der Verteilung der Wartezeit für den Münzwurf, des Erwartungswertes und der Standardabweichung für r = 2 und r = 3.

Aufgabe: Führen Sie die zu Abbildung 6 analogen Berechnungen für r = 4 aus.

2. Beispiel: Würfeln

Ein typisches Glücksspiel besteht darin, so lange zu würfeln bis man eine gewisse Anzahl r von Sechsen gewürfelt hat. Verwendet man einen Laplace-Würfel, beträgt die Trefferwahrscheinlichkeit p = 1/6. Das Glücksspiel ist somit ein Wartezeitproblem im hier diskutierten Sinne und kann auf einen Münzwurf zurückgeführt werden - allerdings mit einer gezinkten Münze mit Trefferwahrscheinlichkeit p = 1/6.

Abbildung 7 zeigt die zu Abbildung 5 analogen Diagramme zu r = 1, 2, 3, 4.

Abbildung 7: Verteilung der Wartezeit für den Münzwurf mit Trefferwahrscheinlichkeit p = 1/6 (wieder für r = 1, 2, 3, 4). Zusätzlich eingetragen sind jeweils Erwartungswert und Standardabweichung der Wartezeiten. Um die Histogramme untereinander vergleichen zu können, ist die Skalierung der Achsen in allen Diagrammen identisch.

Aufgabe: Führen Sie die zu Abbildung 6 analogen Berechnungen für p = 1/6 und r = 1, 2, 3, 4 durch.

Ausblick

Das Wartezeitproblem kann auch auf einer abstrakteren Ebene betrachtet werden, was aber hier nur angedeutet werden soll:

1. Da man die Zufallsvariable X_r,p als Summe von unabhängigen Zufallsvariablen schreiben kann (siehe Gleichung (3) in Abbildung 4), kann man die Verteilung von X_r,p auch über die Faltung der Verteilungen der Summanden berechnen. Das heißt die Wahrscheinlichkeiten P(X_r,p = i) entstehen auch aus der r-fachen Faltung der geometrischen Verteilung (zum Parameter p). Entsprechend kann man die Eigenschaften der Verteilung P(X_r,p = i) aus den Eigenschaften der Faltung und den Eigenschaften der geometrischen Verteilung herleiten.
2. Die Verteilung der Wartezeiten P(X_r,p = i), siehe Gleichung (1) in Abbildung 4, hat eine gewisse Ähnlichkeit mit der Binomialverteilung. Man kann dies zum Anlass nehmen, um eine allgemeinere Klasse von Binomialverteilungen zu definieren. Und diese Verteilungen sind dann über die Faltung mit der geometrischen Verteilung verwandt. Den Zusammenhang zwischen Binomialverteilungen und der geometrischen Verteilung kann man dann weiter untersuchen.