Interpretation der Zufallsexperimente Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen durch Pfade auf einem Gitter

Einordnung des Artikels

• Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
  • Wahrscheinlichkeitsrechnung
    • Spezielle Wahrscheinlichkeitsverteilungen
      • Spezielle Wahrscheinlichkeitsverteilungen: die geometrische Verteilung
      • Spezielle Wahrscheinlichkeitsverteilungen: Lösung von Wartezeitproblemen mit Hilfe der geometrischen Verteilung
      • Spezielle Wahrscheinlichkeitsverteilungen: die hypergeometrische Verteilung
      • Wartezeitprobleme beim Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen
      • Interpretation der Zufallsexperimente Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen durch Pfade auf einem Gitter

In diesem Artikel werden Kenntnisse über folgende Themen vorausgesetzt:

• Binomialkoeffizienten und Binomialverteilung
• geometrische und hypergeometrische Verteilung
• Wartezeitprobleme beim "Ziehen mit Zurücklegen" und "Ziehen ohne Zurücklegen".

Die hier nötigen Kenntnisse über die Binomialverteilung werden in Wartezeitprobleme beim Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen zusammengefasst.

Der Zusammenhang zwischen der Menge aller Pfade und anderer Abzählprobleme wurde in Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars ausführlich dargestellt. Diese Erläuterungen werden hier nicht wiederholt.

Einführung

Die Fragestellungen, die in Wartezeitprobleme beim Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen behandelt wurden, werden hier unter zwei neuen Gesichtspunkten diskutiert:

• Die Zufallsexperimente "Ziehen mit Zurücklegen" und "Ziehen ohne Zurücklegen" werden umformuliert zu einer Zufallsbewegung auf einem Gitter.
• Die Verteilungen, die die Anzahl der Treffer beziehungsweise die Wartezeit bis zum Eintreten des r-ten Treffers beschreiben, werden über dem Gitter dargestellt.

Es werden im Vergleich zum zitierten Artikel keine neuen Ergebnisse gezeigt, aber es soll vermittelt werden, dass die Sichtweise der Zufallsexperimente als Zufallsbewegung auf einem Gitter zu einer besseren Veranschaulichung der Verteilungen und der Beweise führt. Dies liegt daran, dass man viele Fragestellungen auf reine Abzählprobleme zurückführen kann, wofür Zufallsbewegung auf dem Gitter einen intuitiven Zugang liefert.

Bezeichnungen

Zunächst wird ein einfaches Zufallsexperiment betrachtet, nämlich das Ziehen von Losen aus einer Urne, wobei es nur zwei Arten von Losen gibt:

1. Treffer, die auch als 1 bezeichnet werden.
2. Nieten, die als 0 bezeichnet werden.

Es sollen mehrere Lose nacheinander aus der Urne gezogen werden, was auf zwei Arten realisiert werden kann:

1. Ziehen mit Zurücklegen: Jedes entnommene Los wird sofort wieder in die Urne gelegt. Dadurch besteht nach jedem Zug die identische Ausgangssituation.
2. Ziehen ohne Zurücklegen: Ein entnommenes Los wird nicht in die Urne zurückgelegt; die Urne wird sukzessive geleert und die Trefferwahrscheinlichkeit beim nächsten Zug hängt davon ab, welche Lose zuvor gezogen wurden.

Für diese Zufallsexperimente werden einige Bezeichnungen eingeführt, um die Wartezeitprobleme eindeutig formulieren zu können. Anschließend werden diese Bezeichnungen auf ein gleichwertiges Zufallsexperiment übertragen, nämlich die zufällige Bewegung in einem Gitter.

Es wird dann gezeigt, wie die Berechnung der Verteilungen von Wartezeiten (beim Ziehen von Losen aus der Urne) in Abzählprobleme bei der Zufallsbewegung im Gitter verwandelt werden.

Ziehen mit Zurücklegen

Die folgende Tabelle zeigt die heir benötigten Bezeichnungen, die bereits in Wartezeitprobleme beim Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen eingeführt und erläutert wurden; sie sollten ohne ausführliche Erklärung verständlich sein.

Ziehen ohne Zurücklegen

Analog werden jetzt die Begriffe und Variablen beim Ziehen ohne Zurücklegen definiert und in der folgenden Tabelle gezeigt; zu beachten ist jetzt, dass sich die Wahrscheinlichkeiten für Treffer beziehungsweise Niete andauernd verändern.

Ganz analog kann man jetzt beim "Ziehen ohne Zurücklegen" die Zufallsvariable Y_r definieren, die angibt nach wie vielen Ziehungen der r-te Treffer eintritt. Die Zufallsvariable Y_r kann die Werte n = r, r+1, ..., K+r annehmen, denn die Urne enthält nur K Nieten und daher muss nach K+r Ziehungen der r-te Treffer eingetreten sein

Darstellung der möglichen Ziehungen als Pfade im Gitter

Im Folgenden wird gezeigt, wie man die Zufallsexperimenten Ziehen mit Zurücklegen beziehungsweise Ziehen ohne Zurücklegen gleichwertig durch eine Zufallsbewegung in einem Gitter darstellen kann

Ziehen mit Zurücklegen

Definition eines Pfades

Abbildung 1 soll zeigen, wie man das Zufallsexperiment Ziehen mit Zurücklegen interpretieren muss, um die Zufallsbewegung zu erzeugen:

1. Die Bewegung startet im Ursprung (0; 0); er ist im Diagramm in Abbildung 1 grün eingetragen.
2. Wird ein Treffer gezogen, bewegt man sich um eine Einheit in y-Richtung, also ↑.
3. Wird eine Niete gezogen, bewegt man sich um eine Einheit in x-Richtung, also →.

Somit wird jede 01-Folge, die ein Ergebnis beim Ziehen der Lose beschreibt, in einen Pfad im Gitter übersetzt. Werden N Lose gezogen, so muss der Endpunkt des Pfades auf der Geraden

k + l = N

liegen, wobei l die Anzahl der Treffer und k die Anzahl der Nieten angibt. In Abbildung 1 wird für die Zugfolge 01101 der entsprechende Pfad gezeigt, er endet im Punkt (2; 3).

Die Punkte

(0; 5), (1; 4), (2;3), (3;2), (4; 1), (5; 0)

bilden die Menge der möglichen Endpunkte der Pfade, wenn N = 5 ist. Diese Punkte sind im Diagramm in Abbildung 1 orangefarben eingetragen.

Abbildung 1: Veranschaulichung der Pfade im Gitter im Fall "Ziehen mit Zurücklegen" mit Hilfe eines Beispiels einer speziellen Zugfolge.

Die Menge aller möglichen Ergebnisse beim N-maligen Ziehen mit Zurücklegen wird nicht durch die Menge dieser Endpunkte beschrieben, sondern durch die Menge aller Pfade von (0; 0) zu den Endpunkten. Da es bei jedem Zug zwei Möglichkeiten gibt (1 oder 0 beziehungsweise ↑ oder →), gibt es insgesamt 2^N unterschiedliche Pfade.

Die y-Koordinate eines Endpunktes gibt jeweils die Anzahl der Treffer in der Zugfolge an. Somit ist diese Darstellung der Ergebnisse beim Ziehen von Losen aus einer Urne besonders gut geeignet, um Ereignisse der Art "genau l Treffer" zu veranschaulichen.

Erzeugen der Menge aller Pfade durch Rekursion

Da man sich bei jedem Schritt entweder nach rechts → oder nach oben ↑ bewegen kann, ist es nicht schwer, eine Rekursion zu finden, durch die die Menge aller Pfade erzeugt wird. Abbildung 2 soll diese Rekursion veranschaulichen.

Im Fall N = 1 gibt es nur zwei mögliche Pfade: beide starten im Ursprung (0; 0) und enden entweder in (1; 0) oder (0; 1). Sämtliche Endpunkte der Pfade zu N = 1 liegen somit auf der Geraden k + l = 1. Und die Anzahl der Pfade stimmt mit 2 überein.

Hat man zu einem gegebenen N bereits alle Pfade erzeugt, so liegen die Endpunkte auf der Geraden k + l = N. Daraus werden die Pfade zu N + 1 erzeugt, indem man aus jedem Pfad, der in einem Punkt (k; l) endet, zwei neue Pfade erzeugt:

• Ein Pfad mit dem nächsten Schritt nach rechts →.
• Ein Pfad mit dem nächsten Schritt nach oben ↑.

Die neuen Endpunkte haben die Koordinaten (k + 1; l) beziehungsweise (k; l + 1). Und sämtliche derart gebildeten Endpunkte liegen auf der Geraden k + l = N + 1.

Weiter ist klar, dass beim Übergang von N zu N + 1 die Anzahl der möglichen Pfade verdoppelt wird. Denn mit den oben beschriebenen Anweisungen kann kein Pfad doppelt erzeugt werden. Und da dies bei jedem Übergang von N zu N + 1 richtig ist, gibt es zu gegebenem N genau 2^N unterschiedliche Pfade.

Abbildung 2: Veranschaulichung der Rekursion, durch die alle möglichen Pfade auf dem Gitter erzeugt werden. Ebenso kann man aus dieser Überlegung die Anzahl der unterschiedlichen Pfade zu gegebenem N herleiten.

Einführung von Wahrscheinlichkeiten

Oben wurde gesagt, dass die Veranschaulichung der Ergebnisse beim Ziehen von Losen aus einer Urne als Menge von Pfaden vorteilhaft ist. Ein Nachteil dieser Darstellung muss aber auch genannt werden. Das Diagramm in Abbildung 1 ist offensichtlich symmetrisch bei Vertauschung von Treffern und Nieten. Dies kann suggerieren, dass ihre Wahrscheinlichkeiten identisch sind, was im Allgemeinen aber falsch ist.

Die Trefferwahrscheinlichkeit wird mit p bezeichnet und kann jeden Wert zwischen 0 und 1 annehmen. Überträgt man dies auf die Pfade, so ist die Wahrscheinlichkeit für eine Bewegung nach oben gleich p, die Wahrscheinlichkeit für eine Bewegung nach rechts gleich q = 1 - p.

Da die Ziehungen unabhängig voneinander erfolgen und die Trefferwahrscheinlichkeit immer gleich ist, kann man jedem Pfad, der im Punkt (k; l) endet (also ein Pfad mit l Treffern und k Nieten) das statistische Gewicht

p^l·q^k = p^l·q^{N - l}, k, l = 0, 1, ..., N,

zuordnen. Multipliziert man jetzt dieses statistische Gewicht mit der Anzahl der Pfade, die zum Endpunkt (k; l) führen, erhält man – wenn man l die Wert von 0 bis N durchlaufen lässt – die Binomialverteilung. Dieser Gedanke wird weiter unten fortgeführt, zunächst soll das Zufallsexperiment "Ziehen ohne Zurücklegen" untersucht werden, wenn die Ergebnisse durch Pfade dargestellt werden.

Ziehen ohne Zurücklegen

Definition eines Pfades

Das Ziehen mit Zurücklegen kann beliebig oft wiederholt werden – es gibt keine Einschränkung an die Anzahl N der Züge. Dagegen verändern sich beim Ziehen mit Zurücklegen die Anzahlen der Treffer und Nieten in der Urne; somit kann die Anzahl der gezogenen Treffer maximal L betragen, die Anzahl der gezogenen Nieten ist maximal gleich K, und der Urne können maximal N = K + L Lose entnommen werden. Diese Einschränkungen müssen beachtet werden, wenn man die möglichen Pfade und ihre Endpunkte angeben möchte. Abbildung 3 versucht dies zu verdeutlichen.

Im gezeigten Beispiel befinden sich anfangs 5 Lose in der Urne, davon sind

• K = 3 Nieten und
• L = 2 Treffer.

In Beispiel 1 werden N = 3 Lose entnommen, das Ergebnis ist 011 und der Endpunkt des Pfades ist (1; 2). Da die Urne anfangs nur L = 2 Treffer enthält, kann kein Pfad oberhalb der waagrechten Geraden l = 2 liegen (l ist die Anzahl der Treffer); entsprechend auch kein Pfad rechts der lotrechten Gerade k = 3 (k ist die Anzahl der Nieten). Somit gibt es zwei Bedingungen, die die Endpunkte der Pfade erfüllen müssen:

• Jeder Endpunkt zu N Ziehungen muss auf der Geraden k + l = N liegen.
• Jeder Endpunkt muss sich im Rechteck befinden, das von den Punkten (0; 0) und (K; L) aufgespannt wird.

Man kann dies auch anders formulieren: Die möglichen Endpunkte der Pfade sind jetzt nicht mehr alle Punkte auf der Geraden k + l = N, sondern nur noch diejenigen Punkte, die im Rechteck liegen, das von (0; 0) und (K; L) aufgespannt wird (blaues Rechteck in Abbildung 2). Mit " im Rechteck" ist natürlich gemeint, dass sich die Endpunkte auch auf dem Rand des Rechtecks befinden dürfen.

Im Grenzfall N = K + L (die Urne wird komplett geleert wie in Beispiel 2) verbleibt nur noch der Punkt (K; L) als möglicher Endpunkt. Alle Pfade beginnen in (0; 0) und enden in (K; L).

Abbildung 3: Veranschaulichung der Pfade im Gitter im Fall "Ziehen ohne Zurücklegen" mit Hilfe zweier Beispiele.

Erzeugen der Menge aller Pfade durch Rekursion

In Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars wurde gezeigt, wie man – zum Beispiel mit der Beweismethode "Stars and Bars" – die Anzahl der Pfade berechnen kann. Allerdings wurde dort nur das spezielle Problem betrachtet, wenn es nur einen Endpunkt gibt (in der Sprache des Zufallsexperimentes "Ziehen ohne Zurücklegen": die Urne wird vollständig geleert). Die Bezeichnungen wurden dort anders gewählt und müssen entsprechend angepasst werden. Die Berechnung der Anzahl der Pfade erfolgt durch einen Binomialkoeffizienten, den man leicht verstehen kann: Verbindet man die Punkte (0; 0) und ((K; L) durch beliebige Pfade, so besteht jeder Pfad aus K + L Schritten, von denen K Schritte nach rechts und L Schritte nach oben gehen; die Anzahl der Pfade ist dann der Binomialkoeffizient "K aus K+L".

Ebenso wurde dort die Rekursionsformel gezeigt, die für die Anzahl der Pfade gilt; sie ist deutlich komplizierter als die Rekursionsformel für die Anzahl der Pfade beim "Ziehen mit Zurücklegen".

Verzichtet man auf die Zusatzbedingung N = K + L (die Urne wird vollständig geleert), so ist die Berechnung der Anzahl der Pfade sowie die Rekursionsformel zu ihrer Berechnung nochmals komplizierter. Diese Probleme sollen hier nicht diskutiert werden.

Einführung von Wahrscheinlichkeiten

Beim Ziehen mit Zurücklegen beträgt an jeder Stelle im Gitter die Wahrscheinlichkeit dafür, einen Schritt in y-Richtung zu gehen p, und dafür, einen Schritt in x-Richtung zu gehen q = 1 - p. Beim Ziehen ohne Zurücklegen verändern sich die Wahrscheinlichkeiten nach jedem Schritt. Bei geeigneter Wahl von K und L kann man dafür sorgen, dass im Anfangspunkt (0; 0) die Wahrscheinlichkeiten noch mit p = L/M und q = K/M aus dem Zufallsexperiment Ziehen mit Zurücklegen übereinstimmen.

Man kann sich leicht überlegen, dass die veränderten Wahrscheinlichkeiten durch die folgenden Formeln berechnet werden, wenn man sich im Punkt (k; l) befindet:

p (k, l) = (L - l) / (K + L - (k +l)),

q (k, l) = (K - k) / (K + L - (k + l)).

Darstellung der Verteilungen für die Anzahl der Treffer

Bisher wurde gezeigt:

1. Ist die Anzahl N der Ziehungen vorgegeben, so liegt die Menge der möglichen Endpunkte der Pfade auf der Geraden k + l = N. Beim Ziehen mit Zurücklegen können k und l die Werte 0, 1, ..., N annehmen, beim Ziehen ohne Zurücklegen gibt es die weiteren Einschränkungen k ≤ K und l ≤ L.
2. In der Sprache der Ziehung von Losen bedeutet der Endpunkt (k; l), dass k Nieten und l Treffer gezogen werden.
3. Jeder Pfad von (0; 0) nach (k; l) trägt ein statistisches Gewicht, das aus den Treffer- und Nietenwahrscheinlichkeiten berechnet werden kann. Beim Ziehen mit Zurücklegen beträgt es p^l·q^k = p^l·q^{N - l}, beim Ziehen ohne Zurücklegen ist es schwieriger zu berechnen, da sich die Wahrscheinlichkeiten (für Treffer und Niete) entlang des Pfades verändern.

Addiert man jetzt zu jedem Endpunkt (k; l) die statistischen Gewichte aller Pfade von (0; 0) nach (k; l), so entsteht eine Wahrscheinlichkeitsverteilung auf den Punkten der Gerade k + l = N. Dabei wird dem Punkt (k; l) die Wahrscheinlichkeit dafür zugeordnet, dass bei N Ziehungen genau l Treffer (und k = N - l Nieten) erscheinen.

Diese Wahrscheinlichkeitsverteilungen sollen im Folgenden angegeben und über dem Gitter als Histogramm dargestellt werden. Um Ergebnis bereits vorwegzunehmen:

1. Beim Ziehen mit Zurücklegen entsteht die Binomialverteilung (siehe Abbildungen 4 links sowie Abbildungen 5 bis 7).
2. Beim Ziehen ohne Zurücklegen entsteht die hypergeometrischen Verteilung (siehe Abbildung 4 rechts sowie Abbildungen 8 und 9).

Abbildung 4: Die Binomialverteilung und hypergeometrische Verteilung sowie die Darstellung wie sie hier als Verteilung auf den Endpunkten von Pfaden aufgefasst werden. Das Histogramm der Verteilung wird über den Punkten mit ganzzahligen Koordinaten auf der Gerade k + l = N gezeichnet. Dabei muss im Fall "Ziehen ohne Zurücklegen" berücksichtigt werden, dass die Urne nicht beliebig viele Lose enthält und daher die Gerade k + l = N durch das blaue Rechteck beschränkt wird.

Ziehen mit Zurücklegen: die Binomialverteilung

Jeder Pfad von (0; 0) nach (k; l) trägt das statistische Gewicht

p^l·q^k = p^l·q^{N - l}.

Man kann leicht abzählen, wie viele Pfade es von (0; 0) nach (k; l) gibt: Da jede Pfad aus insgesamt k + l Schritten besteht und davon l Schritte in y-Richtung gehen, berechnet sich de Anzahl der möglichen Pfade durch den Binomialkoeffizient "l aus (k+l)".

Daher entsteht als Wahrscheinlichkeitsverteilung die Binomialverteilung B(N = k+l, p, l), l = 0, 1, ..., N, k = N - l. Ihre Eigenschaften wurden in Wartezeitprobleme beim Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen zusammengefasst und daher wird sie hier nicht erläutert; siehe auch Abbildung 4 links.

1. Beispiel: Trefferwahrscheinlichkeit p = 0.5

Eine Trefferwahrscheinlichkeit von p = 0.5 bedeutet, dass mit gleicher Wahrscheinlichkeit ein Schritt in x-Richtung beziehungsweise in y-Achse erfolgt. Im Sinne der Ziehungen von Losen: die Urne enthält gleich viele Treffer und Nieten. Für die Wahrscheinlichkeitsverteilung auf den Endpunkten der Pfade entsteht eine Binomialverteilung B(N, p = 0.5, l), l = 0, 1, .., 10.

Abbildung 5 zeigt diese Binomialverteilung für N = 10 und p = 0.5 als Histogramm; auf der x-Achse sind die Nieten, auf der y-Achse die Treffer aufgetragen. Man erkennt leicht, dass jetzt Treffer und Nieten vertauscht werden können, da die Wahrscheinlichkeitsverteilung identische Werte liefert, wenn man von l zu N - l übergeht. Die Gerade k + l = N ist in der xy-Ebene eingetragen.

Abbildung 5: Es werden N = 10 Lose aus der Urne gezogen (mit Zurücklegen), wobei die Trefferwahrscheinlichkeit p = 1/2 beträgt. Es entsteht eine Binomialverteilung B (N = 10, p = 0.5, l), mit l = 0, ... , 10, die auf der Gerade k + l = N aufgetragen wird (in x-Richtung die Anzahl der Nieten l, in y-Richtung die Anzahl der Treffer k).

Abbildung 6 zeigt dann sämtliche Binomialverteilungen für N = 1, 2, ..., 10; für jede der Verteilungen wird eine eigene Farbe gewählt. Wieder sind die Geraden k + l = N in der xy-Ebene in der Farbe des zugehörigen Histogramms eingetragen.

Abbildung 6: Analog zu Abbildung 5 werden die Binomialverteilungen für N = 1, ..., 10 und einer Trefferwahrscheinlichkeit p = 0.5 aufgetragen. Dabei wird jedes Histogramm zu einem gegebenen N mit einer anderen Farbe dargestellt.

2. Beispiel: Trefferwahrscheinlichkeit p = 1/6

In den Abbildungen 5 und 6 sind die Binomialverteilungen offensichtlich symmetrisch gegenüber der Vertauschung von Treffern und Nieten. Wählt man eine Trefferwahrscheinlichkeit ungleich 1/2, geht diese Symmetrie verloren. In Abbildung 7 wird die Trefferwahrscheinlichkeit p = 1/6 gewählt; wie in Abbildung 6 werden die Histogramme für N = 1, ..., 10 aufgetragen.

Abbildung 7: Wie in Abbildung 6 werden die Binomialverteilungen dargestellt, jetzt aber mit p = 1/6. Es werden N = 10 Lose aus der Urne gezogen (mit Zurücklegen), wobei die Trefferwahrscheinlichkeit p = 1/6 beträgt. Es entsteht für jedes N eine Binomialverteilung B (N , p = 1/6, l), mit l = 0, ... , N, die auf der Gerade k + l = N aufgetragen wird (in x-Richtung die Anzahl der Nieten l, in y-Richtung die Anzahl der Treffer k).

Ziehen ohne Zurücklegen: die hypergeometrische Verteilung

Fragt man beim Ziehen ohne Zurücklegen nach der Anzahl der Treffer bei N Ziehungen, so muss man die Zufallsvariable betrachten, die in Spezielle Wahrscheinlichkeitsverteilungen: die hypergeometrische Verteilung als

Y_{K, L, N}

bezeichnet wurde. Da man jetzt keine (konstante) Trefferwahrscheinlichkeit p angeben kann, muss man die beiden Parameter K und L angeben (Anzahl der Nieten und Treffer, die sich zu Beginn in der Urne befinden). In den Abbildung 8 und 9 werden dann die Wahrscheinlichkeiten

P(Y_{K, L, N} = n)

aufgetragen, wobei n nur die erlaubten Werte 0, 1, ..., min(L, N) annehmen kann. Damit man die Histogramme besser mit den Abbildungen 6 und 7 vergleichen kann, sind K und L jeweils so gewählt, dass anfangs die Trefferwahrscheinlichkeiten p = 0.5 beziehungsweise p = 1/6 betragen.

1. Beispiel: K = 6, L = 6

Abbildung 8 zeigt die zu Abbildung 5 analoge Darstellung der Verteilungen, wenn die Urne anfangs mit K = 6 Nieten und L = 6 Treffern gefüllt ist. Die Anzahl der Ziehungen kann jetzt N = 1, ..., 12 betragen.

Betrachtet wird jeweils die Zufallsvariable Y_{K, L, N}, die die Anzahl der Treffer bei N Ziehungen beschreibt. Die beiden Indizes K und L geben die Anzahl der Nieten beziehungsweise Treffer an, mit denen die Urne anfangs gefüllt ist.

Speziell für N = 12 wird die Urne vollständig geleert und die entstehende Verteilung ist auf den Punkt (6; 6) konzentriert. Für kleinere N liegen die möglichen Endpunkte der Pfade innerhalb des von (0; 0) und (6; 6) aufgespannten Rechtecks, das in Abbildung 8 nur noch schwer zu erkennen ist.

Die Verteilungen von Y_{K, L, N} auf den Endpunkten der Pfade sind jetzt jeweils die hypergeometrischen Verteilungen, die in Spezielle Wahrscheinlichkeitsverteilungen: die hypergeometrische Verteilung ausführlich diskutiert wurden.

Beim ersten Zug ist die Trefferwahrscheinlichkeit p gleich 0.5, sie ändert sich aber im Laufe der weiteren Ziehungen. Die Anzahlen der Treffer und Nieten in der Urne wurden so gewählt, dass man Abbildung 8 mit Abbildung 6 vergleichen kann.

Abbildung 8: Wie in Abbildung 6 wird jetzt die hypergeometrische Verteilung für die Werte von N = 1, 2, ..., 12 mit jeweils einer eigenen Farbe dargestellt. Die Urne ist anfangs so bestückt (K = 6 = L), dass beim ersten Zug die Trefferwahrscheinlichkeit p = 0.5 beträgt.

2. Beispiel: K = 2, L = 10

Analog zum ersten Beispiel wird die Urne so bestückt, dass anfangs die Trefferwahrscheinlichkeit p = 1/6 beträgt.

Abbildung 9: Darstellung der hypergeometrischen Verteilungen analog zu Abbildung 8, jetzt mit K = 2 und L = 10. Damit ist die Trefferwahrscheinlichkeit zu Beginn gleich 1/6, womit man die Histogramme besser mit Abbildung 7 vergleichen kann.

Aufgabe:

Identifizieren Sie in den Abbildungen 8 und 9 jeweils die Rechtecke, die von (0; 0) und (K; L) aufgespannt werden.

Darstellung der Verteilungen für die Wartezeiten bis zum r-ten Treffer

In Wartezeitprobleme beim Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen wuden die mit den Zufallsexperimenten "Ziehen mit Zurücklegen" beziehungsweise "Ziehen ohne Zurücklegen" verbundenen Wartezeitprobleme diskutiert. Mit "Wartezeitproblem" ist gemeint:

• Man gibt eine natürliche Zahl r vor und fragt nach der Wahrscheinlichkeit dafür, dass nach genau n Zügen der r-te Treffer eintritt.
• Beim "Ziehen mit Zurücklegen" können r und n beliebige natürliche Zahlen annehmen – mit der einzigen Einschränkung, dass n größer oder gleich r sein muss. Da beliebig viele Nieten erscheinen können, kann n auch beliebig große Werte annehmen.
• Beim "Ziehen ohne Zurücklegen" gibt es weitere Einschränkungen: die Zahl r kann nicht größer als L gewählt werden und n kann K + r nicht übersteigen.

Die Zufallsvariablen, welche die Wartezeit bis zum r-ten Treffer beschreiben, werden wie im zitierten Artikel mit W_r beziehungsweise Y_r bezeichnet. Die Berechnung der Wahrscheinlichkeiten

P(W_r = n) beziehungsweise P(Y_r = n)

wurde dort auf Abzählprobleme zurückgeführt. Diese Abzählprobleme können mit der Sichtweise der "Pfade auf dem Gitter" besser veranschaulicht werden. Die Vorgehensweise und die wichtigsten Resultate werden in Abbildung 10 gezeigt und in den folgenden Unterabschnitten erläutert.

Abbildung 10: Das Wartezeitproblem in der Sichtweise der Pfade auf einem Gitter.

In den Diagrammen in Abbildung 10 wird versucht das Ereignis

W_r = n beziehungsweise Y_r = n

darzustellen. Soll genau beim n-ten Zug der r-te Treffer eintreten, so bedeutet dies in der Sichtweise der Pfade auf dem Gitter:

• Im n-ten Schritt muss man sich in y-Richtung bewegen ↑.
• In den n-1 vorhergehenden Schritten erfolgen dann r-1 Schritte in y-Richtung ↑ und k = n-r Schritte in x-Richtung →. Diese n-1 Schritte können in beliebiger Reihenfolge geschehen.
• Somit verlaufen alle erlaubten Pfade durch die drei Punkte (0; 0), (k; r-1) und (k; r).

In Abbildung 10 wird die Menge aller Pfade von (0; 0) nach (k; r-1) durch das rote Gitter angedeutet; der letzte Schritt ↑ muss dann von (k; r-1) nach (k; r) erfolgen.

Ziehen mit Zurücklegen

Um die Wahrscheinlichkeit eines Ereignisses P(W_r = n) zu berechnen, kann man jetzt wieder folgendermaßen vorgehen:

• Man identifiziert die zugehörigen Pfade im Diagramm in Abbildung 10 links; jeder Pfad endet im Punkt (k; r) mit k = n - r.
• Jedem Pfad wird ein statistisches Gewicht zugeordnet. Da jeder Pfad mit Endpunkt (k; r) aus r Schritten ↑ und k = n - r Schritten → besteht, beträgt das statistische Gewicht für jeden Pfad p^rq^{n - r}.
• Die Anzahl der Pfade, die zum Ereignis W_r = n gehören, lässt sich leicht abzählen: es ist der Binomialkoeffizient in P(W_r = n) in Abbildung 10 links unten.

Insgesamt erhält man die Formel in Abbildung 10.

1. Beispiel: p = 0.5

Die Trefferwahrscheinlichkeit betrage p = 0.5. Für de Werte r = 1, 2, ..., 7 zeigt Abbildung 11 die Verteilungen der Zufallsvariablen W_r, wobei für jedes r eine andere Farbe gewählt wird. Die Histogramme sind an den entsprechenden Endpunkten der Pfade eingetragen, nämlich die Wahrscheinlichkeit P(W_r = n) im Punkt (k; r) mit k = n - r.

Abbildung 11: Verteilung der Wartezeiten beim Ziehen mit Zurücklegen für p = 0.5 und r = 1, 2, ..., 7.

Den qualitativen Verlauf der Verteilungen in Abbildung 11 kann man jetzt leicht in der Sichtweise der "Pfade auf dem Gitter" erklären.

Für r = 1 gilt:

• Zu jedem Endpunkt (k; 1) gibt es genau einen Pfad; er besteht aus k Schritten nach rechts → und einem letzten Schritt nach oben ↑.
• Das statistische Gewicht jedes Pfades ist pq^k.
• Somit stimmt hier das statistische Gewicht mit der Wahrscheinlichkeit für die Wartezeit "W₁ = n = k-1" überein.
• Als Funktion von n ist die Wahrscheinlichkeit P(W₁ = n) somit streng monoton fallend.

Für r = 2, 3, ... muss man die Argumentation ein wenig abwandeln – und kann dann leicht erklären, warum die Verteilungen ein deutliches Maximum besitzen:

• Die Anzahl der Pfade, die zu einem Ereignis W_r = n gehören ist jetzt größer als 1. Man kann die Menge dieser Pfade durch das Rechteck im Diagramm in Abbildung 10 links veranschaulichen (als Gitter gezeichnet, um alle möglichen Pfade anzudeuten).
• Da mit zunehmendem n diese Rechtecke immer größer werden, gibt es mehr Möglichkeiten den Endpunkt (r-1; k) des Rechtecks zu erreichen. Als Funktion von n aufgefasst, ist die Anzahl der Pfade streng monoton zunehmend.
• Das statistische Gewicht der Pfade berechnet sich durch p^rq^{n - r} und ist als Funktion von n wieder streng monoton fallend.
• Multipliziert man jetzt die Anzahl der Pfade mit dem statistischen Gewicht, erhält man eine Funktion von n, die ein Maximum besitzt. Es ist allerdings nicht klar, ob es nicht mehrere Werte von n gibt, die den gleichen Maximalwert annehmen.

Aufgabe: Wie kann man diese Argumentation jetzt verwenden, um zu zeigen, dass sich bei zunehmendem r die Lage des Maximums der Verteilung von W_r immer weiter nach rechts verschiebt?

2. Beispiel: p = 1/6

Abbildung 12 zeigt die analoge Darstellung zu Abbildung 11, wenn die Trefferwahrscheinlichkeit p = 1/6 gewählt wird. Der exponentielle Abfall erfolgt jetzt langsamer, ansonsten stimmt das qualitative Verhalten mit denen Verteilungen aus Abbildung 11 überein.

Abbildung 12: Verteilung der Wartezeiten beim Ziehen mit Zurücklegen für r = 1, 2, ..., 7, p = 1/6.

Ziehen ohne Zurücklegen

Berechnung der Verteilung der Wartezeiten

In Wartezeitprobleme beim Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen wurden zwei Möglichkeiten gezeigt, wie man die Verteilung der Wartezeiten beim Ziehen ohne Zurücklegen herleiten kann. Insbesondere der Zugang durch Abzählen der möglichen Ergebnisse lässt sich mit Hilfe der Pfade auf dem Gitter sehr gut veranschaulichen. In Abbildung 13 wird versucht, die wichtigsten Schritte darzustellen.

Wird die Urne vollständig geleert, so entspricht dies einem Pfad von (0; 0) nach (K; L). Die Menge all dieser Pfade entspricht der Menge aller möglichen Ziehungen. Ihre Anzahl wird durch den Binomialkoeffizient "K aus K + L" beziehungsweise "L aus K + L" berechnet, da man die K Nieten beziehungsweise L Treffer auf die K + L Stellen verteilen muss.

Gibt man eine natürliche Zahl 1 ≤ r ≤ L vor, so gibt es zu jedem dieser Pfade genau eine natürliche Zahl 0 ≤ k ≤ K, so dass der Pfad durch die beiden Punkte (k; r - 1) und (k; r) verläuft. (Gibt es kein derartiges k oder mehrere dieser k, so kann man leicht einen Widerspruch konstruieren: Entweder der Endpunkt (K; L) kann nicht erreicht werden oder man müsste sich einen Schritt entgegen den beiden erlaubten Richtungen bewegen.) Die Menge aller Pfade von (0; 0) nach (K; L) wird somit in K + 1 disjunkten Mengen von Pfaden zerlegt. Die Darstellung mit Hilfe der roten Gitter in Abbildung 13 (für k = 0, ein beliebiges k und k = K) soll diese disjunkten Mengen andeuten. Und es sollte klar sein, dass diese Zerlegung in disjunkte Mengen davon abhängt, wie r gewählt wird.

Abbildung 13: Veranschaulichung der Herleitung der Verteilung der Wartezeiten beim Ziehen ohne Zurücklegen. genauere Erklärung im Text.

Die Anzahl der Pfade von (0; 0) nach (K; L) kann man wie bereits gesagt mit Hilfe eines Binomialkoeffizienten berechnen; sie kann aber auch als eine Summe über k geschrieben werden, wobei die in Abbildung 13 angedeuteten Mengen von Pfaden verwendet werden.

Dazu bezeichnet A((a; b) → (c; d)) die Anzahl der Pfade von (a; b) nach (c; d). Mit dieser Schreibweise lässt sich die Zerlegung in disjunkte Mengen von Pfaden als die Summe in Gleichung (1) in Abbildung 13 darstellen.

Interpretiert man zu einem gegebenen r das Produkt

A((0; 0) → (k; r-1)) · A((k; r) → (K; L))

im Sinne des Zufallsexperimentes Ziehen ohne Zurücklegen, so steht es für folgendes Ereignis:

• Die Urne besitzt anfangs K Nieten und L Treffer und wird vollständig geleert.
• Bei den ersten k + r − 1 Ziehungen treten genau k Treffer ein.
• Im (k+r)–ten Zug wird ein Treffer gezogen.
• Anschließend wird die Urne geleert, wobei die noch vorhandenen Treffer und Nieten in beliebiger Reihenfolge erscheinen können.

Kurz kann man dieses Ereignis auch beschreiben als:

"Der r-te Treffer erscheint genau im n-ten Zug",

wobei n = k + r.

Allerdings bezieht sich dies auf das Zufallsexperiment, bei dem die Urne vollständig geleert wird, nicht auf das Zufallsexperiment, bei dem nach dem r–ten Treffer abgebrochen wird. Da aber nach dem r–ten Treffer beliebige Ergebnisse eintreten können, ist es für die Berechnung der Wahrscheinlichkeit unerheblich, ob man nach dem r-ten Treffer die Ziehungen abbricht oder alle möglichen Ziehungen bis zum Entleeren der Urne betrachtet.

Um jetzt von der Anzahl der Ergebnisse auf eine Wahrscheinlichkeit zu schließen, benötigt man noch die Wahrscheinlichkeiten der einzelnen Zugfolgen, die durch einen Pfad repräsentiert werden. Wird beim Ziehen ohne Zurücklegen die Urne vollständig geleert, so hat jedes mögliche Ergebnis die gleiche Wahrscheinlichkeit, da die Lose lediglich in unterschiedlicher Reihenfolge gezogen werden.

Als Verteilung für die Wartezeit bis zum r-ten Treffer erhält man damit Gleichung (2) in Abbildung 13. Und setzt man jetzt für die Anzahlen A() die entsprechenden Binomialkoeffizienten ein, erhält man den Ausdruck in Gleichung (3). (Diese Verteilung war schon in Abbildung 10 rechts unten gezeigt.)

Aufgabe:

Welche Binomialkoeffizienten müssen in Gleichung (2) in Abbildung 13 eingesetzt werden? Verifizieren Sie damit Gleichung (3).

Wie zeigt man mit Hilfe der Überlegungen aus Abbildung 13, dass die Wahrscheinlichkeiten in Gleichung (3) tatsächlich eine Verteilung bilden, also die Summe aller Wahrscheinlichkeiten 1 ergibt (bei Summation über alle erlaubten n)?

Darstellung der Verteilung der Wartezeiten

Es ist jetzt naheliegend, die Verteilung der Wartezeiten beim Ziehen mit Zurücklegen und beim Ziehen ohne Zurücklegen miteinander zu "vergleichen". Ein echter Vergleich ist natürlich unmöglich, das sich beim Ziehen ohne Zurücklegen die Wahrscheinlichkeiten für Treffer und Niete nach jedem Zug ändern. Aber man kann die Anzahlen der Treffer und Nieten in der Urne so wählen, dass im ersten Zug p und q für beide Zufallsexperimente identisch sind.

1. Beispiel: K = 35, L = 35

In Abbildung 14 werden die Verteilungen der Wartezeiten Y_r für r = 1, 2, ..., 7 gezeigt. Qualitativ stimmen die Verteilungen sehr gut mit denen aus Abbildung 11 überein (dort waren die Wartezeiten W_r beim Ziehen mit Zurücklegen mit p = 1/2 gezeigt):

• Für r = 1 erhält man eine mit der Anzahl n der Ziehungen streng monoton abnehmende Verteilung.
• Für r ≥ 2 besitzen die Verteilungen ein Maximum.

Abbildung 14: Verteilung der Wartezeiten beim Ziehen ohne Zurücklegen für r = 1, 2, ..., 7.

Beim Ziehen mit Zurücklegen war die Erklärung für dieses Verhalten sehr einfach: die Wahrscheinlichkeit kann als Produkt eines statistischen Gewichtes der Pfade und deren Anzahl beschrieben werden. Durch Diskussion der n-Abhängigkeit der beiden Faktoren kann man auf das Verhalten der Verteilung schließen. Dass diese Erklärung hier abgewandelt werden muss, zeigt das nächste Beispiel.

2. Beispiel: K = 7, L = 7

In Abbildung 15 werden wie in Abbildung 14 die Verteilungen der Wartezeiten Y_r für r = 1, 2, ..., 7 gezeigt. Die Urne ist wieder so konfiguriert, dass anfangs die Trefferwahrscheinlichkeit gleich 1/2 ist. Qualitativ erkennt man, dass das Monotonieverhalten jetzt deutlich komplizierter ist.

Abbildung 15: Verteilung der Wartezeiten beim Ziehen ohne Zurücklegen für r = 1, 2, ..., 7. Im Vergleich zu Abbildung 14 werden jetzt die Verteilungen für alle erlaubten Werte von r aufgetragen.

Zwischen Abbildung 14 und 15 besteht ein entscheidender Unterschied: Im ersten Beispiel gibt es anfangs L = 35 Treffer in der Urne, das heißt die Zufallsvariable Y_r kann für r = 1, 2, ..., L = 35 definiert werden; gezeigt sind aber nur die Verteilungen für die Werte r = 1, 2, ..., 7. Diese Verteilungen sind dort deutlich von null verschieden, wo nur wenige Lose aus der Urne entnommen werden (wenig bedeutet hier wenig im Vergleich zur Anzahl der vorhandenen Lose). Aber dann stimmen die Treffer- und Nietenwahrscheinlichkeiten noch sehr gut mit p = q = 0.5 überein.

Ist dagegen r etwa so groß wie L, so wird der r-te Treffer mit hoher Wahrscheinlichkeit erst nach etwa 2·r Zügen eintreten – es verwundert also nicht, dass hier Y₃₅ ein anderes Monotonieverhalten hat als Y_r für kleine Werte von r.

3. Beispiel: K = 35, L = 7

In Abbildung 16 werden die Verteilungen der Wartezeiten für r = 1, ..., 7 dargestellt, wenn die Trefferwahrscheinlichkeit zu Beginn p = 1/6 beträgt

Abbildung 16: Verteilung der Wartezeiten beim Ziehen ohne Zurücklegen für r = 1, 2, ..., 7, wobei die Urne so bestückt ist, dass anfangs die Trefferwahrscheinlichkeit p = 1/6 beträgt.

Aufgabe: Beschreiben Sie die Unterschiede und Gemeinsamkeiten der Verteilungen aus den Abbildungen 14 bis 16.

4. Beispiel: K = 15, L = 3

In Abbildung 16 erkennt man eine Symmetrie zwischen den Verteilungen der Wartezeiten; sie wird noch deutlicher, wenn man für K und L kleinere Werte wählt. Für Abbildung 17 wurde die Urne wie im 3. Beispiel so bestückt, dass anfangs die Trefferwahrscheinlichkeit p = 1/6 beträgt. Da aber nur L = 3 Treffer in der Urne sind, kann r lediglich die Werte r = 1, 2, 3 annehmen. Die Verteilungen der Wartezeiten sind jetzt:

• streng monoton abnehmend für r = 1,
• besitzen ein ausgeprägtes Maximum für r = 2 und
• sind streng monoton zunehmend für r = 3.

Abbildung 17: Verteilung der Wartezeiten beim Ziehen ohne Zurücklegen für r = 1, 2, ..., 7. Wie in Abbildung 16 beträgt die Trefferwahrscheinlichkeit anfangs p = 1/6, die Urne enthält aber weniger Lose.

Aufgabe:

1. Werten Sie Gleichung (3) in Abbildung 13 für Beispiel 4 aus und bestätigen Sie das in Abbildung 17 erkennbare Monotonieverhalten. (Hinweis: Man erhält für alle drei Wartezeitverteilungen quadratische Funktionen in n, wobei n die Anzahl der Ziehungen ist.)

2. Formulieren Sie, welche Symmetrie die Verteilungen der Wartezeiten in Abbildung 16 und 17 besitzen.

Symmetrie der Wartezeitverteilungen

Die Abbildungen 16 und 17 suggerieren, dass die Wartezeitverteilungen folgendes Symmetrieverhalten besitzen. Die Wahrscheinlichkeiten liefern identische Werte wenn man folgende Transformationen durchführt:

r → L - (r-1) = L - r + 1

n → K + L - (n - 1) = K + L + 1 - n.

Das heißt es gilt:

P(Y_r = n) = P(Y_{L - r + 1} = K + L + 1 - n).

In der Sichtweise der Pfade auf dem Gitter ist die Erklärung für diese Symmetrie besonders einfach: Erscheint zum Beispiel im zuletzt diskutierten Beispiel mit K = 15 und L = 3 das Ergebnis (1 steht für Treffer oder ↑, 0 für Niete oder →)

001110000000000000,

so wird im dritten Zug der erste Treffer gezogen, das Elementarereignis gehört somit zum Ereignis

Y₁ = 3.

Liest man das Elementarereignis rückwärts, also

000000000000011100,

so kann es interpretiert werden als: "im 16. Zug erscheint der dritte Treffer"; es tritt also das Ereignis

Y₃ = 16

ein. Und es gilt:

K + L = 18, n = 3, r = 1 und daher

L - r + 1 = 3 - 1 + 1 = 3 und K + L + 1 - n = 18 + 1 - 3 = 16.

Bildet man nun zu jedem Elementarereignis von

Y₁ = 3

die Umkehrung (im Sinne von "rückwärts lesen"), so erhält man sämtliche Elementarereignisse zu

Y₃ = 16.

Und da jedes Elementarereignisse das identische statistische Gewicht trägt (die Urne wird jeweils vollständig geleert), stimmen die entsprechenden Wahrscheinlichkeiten überein. Diese Argumentation stimmt nicht nur für das gewählte Beispiel von K, L, r und n sondern für alle erlaubten derartigen Zahlen.