Das Münzwurfproblem

eine Aufgabe von Stefan Bartels

Gymnasium Winsen/Luhe
Im Mathematikleistungskurs hat Lehrer Karl heute die neuen EURO-Münzen in den Mittelpunkt des Geschehens gerückt. Wirft man eine Münze so erhält man das Ereignis Zahl mit der Wahrscheinlichkeit von p = 1 ÷ 2. Wird die Münze zweimal hintereinander geworfen und man erwartet zweimal das Ereignis Zahl so beträgt die Wahrscheinlichkeit dafür:
                        1
P (ZZ) =  P(Z) .P (Z) =  --
                        4
(1)
Das sind natürlich Trivialitäten für Karl’s Mathematikleistungsschüler. Deshalb hat er seine Aufgabenstellung geringfügig erweitert :
  1. Berechne die mittlere Anzahl an Münzwürfen, bis das erste Mal das Ereignis zweimal Zahl (ZZ) eintritt.
  2. Eine Münze wird so lange geworfen, bis dreimal hintereinander Zahl erscheint. Wie wiele Würfe sind im Durchschnitt dafür notwendig ?
  3. Ermittle durch Computersimulation die Erwartungswerte für die Ereignisse k-mal hintereinander Zahl für 1 < k < 5. Versuche für die Folge der Erwartungswerte eine explizite Formel abzuleiten.

Punktezahl=10

Computersimulation I

Wir beginnen unsere Untersuchungen mit einem kleinen Programm in ARIBAS. ARIBAS ist ein frei programmierbarer Zahleninterpreter der im Internet kostenlos zur Verfügung steht :
http://www.mathematik.uni-muenchen.de/~forster/sw/aribas.html
Das Programm kann quasi unendlich lange Integerzahlen verarbeiten und eignet sich für kombinatorische Untersuchungen sehr gut. Die Programmiersprache entspricht fast identisch MODULA-2. Die Funktion muenze1 simuliert einen n- maligen Versuch eine Münze zu werfen bis das Ereignis Zahl k- mal hintereinander eintrifft. Während aller Versuche wird die Gesamtzahl der Münzwürfe in der Variablen s aufsummiert. Am Ende wird der Quotient s ÷ n zurückgegeben, welcher gerade der gesuchte Erwartungswert ist.

 function muenze1(k, n : integer) : real;
 var s:=0;
     i,z: integer;
 begin
  for i:=1 to n do
     z:=0;
     while z < k do
       inc(s);
       if random(2)=1 then inc(z); else z:=0; end;
     end;
  end;
  return s/n;
 end;
Für n = 100.000 erhalten wir folgendes Ergebnis :







k 1 2 3 4 5 6







E 2 6 14 30 64 126









Die numerischen Daten der Erwartungswerte wurde zum nächstliegenden Integerwert auf- b.z.w. abgerundet. Scharfes hinsehen auf die Tabelle ergibt für den Erwartungswert die Formel:
E[k] := 2k+1- 2,     k > 1
(2)

Kombinatorische Untersuchung von Stephan Bartels

Die Zufallsvariable X habe die Bedeutung Anzahl der Würfe bis zum ersten Mal zweimal hintereinander Zahl (ZZ) erscheint. Gesucht ist der Erwartungswert E(X). Empirisch ergibt sich E(X) = 6 aus der Computersimulation. Die Wahrscheinlichkeiten für die ersten xi lassen sich sofort angeben:

Betrachtet man die Zähler der Quotienten erkennt man die Fibonnaci-Zahlenfolge, während der Nenner aus aufsteigendern Zweierpotenzen besteht. Allgemein müssen für xi > 2 die letzten drei Ergebnisse WZZ sein, während vorher niemals ZZ aufgetreten sein darf. Allgemein gilt damit:

P (X =  xi) = 1---P(X--<=--xi--3)-
                     8
(3)
Man kommt dann auf folgende allgemeine Darstellung:
P (X =  n) = Fn-1-
              2n
(4)
wobei Fm die m-te Fibonacci-Zahl und F0 := 0 ist. Der Beweis erfolgt durch Induktion, wobei gleichzeitig
             Fn+2
P (X <  n) = -2n--
(5)
mitbewiesen wird und die Gleichung (4) verwendet wird. Dieses Ergebnis ist schon recht überraschend, denn wer hätte damit gerechnet, das man im Stochastik-Bereich auf die Fibonacci-Zahlen stößt! Zur Berechnung des Erwartungswerts benötigt man die explizite Darstellung der Fibonacci-Zahlen nach Jacques Philippe Binet (1786-1856):
         ((      V~ -)i   (      V~ -)i)
F  =  V~ 1-    1+---5-  -   1-----5
  i    5        2            2
(6)
und die Summenformel
 sum 
    n .an = ---a----
            (1- a)2
(7)
Nach umfangreichen Umformungen ergibt sich tatsächlich E(X) = 6.

Computersimulation II für den Fall dreimal Zahl hintereinander

Wir erweitern die Funktion muenze1 und registriern die Anzahl der Treffer, die nach dem 2., 3., . . . 10. Wurf in WZZZ enden.
 
 function muenze2(k, n : integer) : array;
 var s:=0;
     p:=2;
     i,j,z: integer;
     y,w : array[11];
 begin
   for i:=1 to 10 do y[i]:=0; w[i]:=0.0; end;
   for i:=1 to n do
     z:=0; j:=0;
     while z < k do
       inc(j);inc(s);
       if random(2)=1 then inc(z); else z:=0; end;
     end;
     if j=2 then inc(y[2]); continue; end;
     if j=3 then inc(y[3]); continue; end;
     if j=4 then inc(y[4]); continue; end;
     if j=5 then inc(y[5]); continue; end;
     if j=6 then inc(y[6]); continue; end;
     if j=7 then inc(y[7]); continue; end;
     if j=8 then inc(y[8]); continue; end;
     if j=9 then inc(y[9]); continue; end;
     if j=10 then inc(y[10]); continue; end;
   end;
   for i:=2 to 10 do
      p:=p*2;
      w[i]:=y[i]*p/n;
   end;
   w[0]:=s/n;
   return w;
 end;
Für ZZZ, d.h. k = 3 und n = 106 ergibt sich:











i 2 3 4 5 6 7 8 9 10










Ti 0 1 1 2 4 7 13 24 44











Hier ist Ti schwieriger abzulesen. Immerhin handelt es sich um eine Differenzenfolge dritter Ordnung die sogenannte Tribonacci-Folge mit dem rekursiven Bildungsgesetz:

Ti = Ti-3 + Ti- 2 + Ti-1, i > 3
(8)
Für die Wahrscheinlichkeiten gilt :

                                    sum  oo 
Pi[ZZ] =  Ti+2,  -->    EW  [ZZZ]  :=    Ti+2
           2i                      i=0  2i
(9)
Das explizite Bildunggesetz für die Differenzenfolge Ti kann aus den Nullstellen des charakteristischen Polynom’s bestimmt werden.
0 = m3 -  m2 - m - 1
(10)
Mit Hilfe eines Computeralgebraprogramms oder den Cardanischen Formeln berechnen wir die Nullstellen:

      1-  1-        V~ --1/3   1-       V~ ---1/3
m1  = 3 + 3 (19- 3   33)  +  3 (19 + 3 33)  ,                  (11)

      1-  1-       V~ --        V~ --1/3  1-        V~ --        V~ --1/3
m2  = 3 - 6 (1+ I   3)(19- 3  33)   - 6 (1-  I  3)(19+ 3  33)   ,
                                                               (12)

      1   1        V~ --        V~ --1/3  1         V~ --        V~ --1/3
m3  = --- --(1- I   3)(19- 3  33)   - --(1+  I  3)(19+ 3  33)
      3   6                           6
                                                               (13)

Das Bildungsgesetz für die Tribonacci-Folge folgt aus dem allegemeinen Ansatz:

Tk = c1 .m1k + c2 .m2k + c3 .m3k,  T1 = 0, T2 = 1, T3 = 1
(14)
Die Konstanten c1, c2, c3 müssen so bestimmt werden, das die Anfangsbedingung erfüllt ist. Im Internet findet man unter www.mathworld.com die fertige Lösung:

       (   V~ ------ V~ ---    V~ ----- V~ ---   )k  V~ --------V ~ --
      3  1 319 + 3  33+ 1 3 19- 3  33 + 1   3 586+ 102  33
Tk =  ---3-- V~ ----------3------------ V~ -3------------------
            3 (586+  102 V~ 33)2 + 4 - 2 3586 + 102 V~ 33
(15)
Der Erwartungswert ergibt sich wieder als unendliche Summe über alle Wahscheinlichkeitswerte :

                      (   V~ ----------     V~ ----------   )     V~ -------------
              sum  oo  2-k 3 1 319 + 3 V~ 33-+ 1 3 19- 3 V~ 33-+ 1 k+2 3 586+ 102 V~ 33
EW  [ZZZ]  :=     -------3- V~ -----------3----------- V~ --3--------------------
              k=0           3(586 + 102 V~ 33)2 + 4 - 2 3 586+ 102  V~ 33
(16)
EW  [ZZZ]  :=  14
(17)

Lösungsweg von Stefan Kirchner , Humbolt Universität Berlin

Wir betrachten einen Graphen, wie er in Abbildung 1 gezeigt ist.


PIC
Abbildung 1: Zustandsgraph für das Ereignis ZZ

Im Zustand 1 liege der Start. Mit einer Wahrscheinlichkeit von 1 ÷ 2 wird entschieden ob Kante Z oder K benutzt wird. Hat man Zahl geworfen, ist man im Zustand 2. Von hier gibt es wieder genau zwei Möglichkeiten K oder Z. Gewonnen hat man, bei Erreichen des Zustandes 3. In diesem Fall hat man zum ersten Mal zwei Z-Kanten hintereinander durchlaufen. Der Graph simuliert also genau das Problem aus Frage (1). Die Anzahl der Kanten, die waehrend einer Reise - im englischen ein sogenannter random walk - durchlaufen wurden, ist genau die Anzahl der Wuerfe, die bis zum Ereignis ZZ erstmalig benötigt wurden.

Wie sehen diese Graphen fuer k-maliges Z aus? Diese können wir jetzt rekursiv für höhere k erzeugen. Den Graphen für (k + 1) erhält man, indem man von Zustand k eine Z-Kante zum neuen Zustand k + 1 führt und eine K-Kante vom Zustand k in den Anfangszustand 1 zurückführt. Für k = 3 zeigt Abbildung 2 den Graphen :


PIC

Abbildung 2: Zustandsgraph für die Simulation k - mal hintereinander Zahl werfen

Berechnungsweg 1
Sei E[Zk] der Erwartungswert der Schritte die man braucht, um von Zustand 1 zum Zustand k zu kommen. Dann gilt :
                                     (  )2
E[Z    ] = E[Z ]+ 1 + 1-(E[Z ]+ 1) +  1-   (E[Z ]+ 1) + ...
    k+1       k       2     k         2        k
(18)
  1. Summand: ich haben den Zustand k genau einmal besucht, d.h. die ersten 0-male hatte ich Pech und landete in Zustand Z1 und danach hatte ich Glueck und landete in Zustand k+1.
  2. Summand: ich haben den Zustand k genau zweimal besucht, d.h. das erste mal hatte ich Pech und landete in Zustand 1 und danach hatte ich Glück und landete in Zustand k + 1.
  3. Summand: ich haben den Zustand k genau dreimal besucht, d.h. die ersten 2-male hatte ich Pech und landete in Zustand 1 und danach hatte ich Glueck und landete in Zustand k+1.

Gleichung (2) in Summenschreibweise lautet :

            oo  (  )                           oo  (  )
            sum    1-i                          sum    1- i
E[Zk+1] =       2   (E[Zk]+ 1) = (E[Zk]+ 1)      2   = 2 (E[Zk] + 1)
           i=0                               i=0
(19)
Diese Rekursionsformel für den Erwartungswert stellt eine lineare Differenzengleichung 1. Ordnug dar. Wir lösen die Gleichnug für den Anfangswert E[Z0] = 0 , denn wir Null mal die Münze werfen ist der Erwartungswert Null.
                                                 k+1
E[Zk+1] =  2(E[Zk]+  1),E[Z0] = 0   -->    E[Zk] = 2   - 2
(20)
Für die ersten fünf Fälle erhalten wir :

E[Z1  = 2,  E[Z2] = 6,  E[Z3] = 14,  E[Z4] = 30,  E[Z5] = 62
(21)
Berechnungsweg II
Jetzt noch eine andere Methode, die ich persoenlich ein wenig eleganter finde. Der Einfachheit halber numerieren wir die Zustaende um, d.h. was vorher k war, ist jetzt 1, k - 1 wird zu 2 usw. Sei E[Ak] der Erwartungswert fuer die Anzahl Besuche von Zustand k, dann gilt:

              sum k
E[Agesamt] =    E[Ak]
             i=1
(22)

Daraus folgt :

              k          k
              sum           sum    i   k+1
E[Agesamt] =    E[Ak] =     2 = 2    - 1
             i=1         i=1
(23)
Wenn ich aber 2k+1 - 1 Zustäende besucht habe, dann habe ich genau 2k+1 - 2 Kanten besucht, und das ist gerade meine erwartete Zeit.
Bemerkung 1
Die Wahrscheinlichkeit, ZZ oder ZK zu werfen, ist gleich gross. Wenn man aber die Erwartungswerte betrachtet, wann zum ersten mal ZZ oder ZK erscheint, so sind sie unterschiedlich gross. Das wird auch am Graphen deutlich:
PIC
Abbildung 3: Zustandsgraph für die Simulation ZZ und ZK

Beim ersten Graphen geht man bei Kopf immer an den Anfang, beim zweiten Graphen wird nie mehr der Zustand 1 erreicht, sobald er einaml verlassen wurde. Damit wird der Zustand 3 schneller erreicht. Interessant ist es jetzt, welche k-Folge den geringsten Erwartungswert hat. Wie sehen die Verteilungen aus. Tritt dieser Effekt asympotitisch noch in Erscheinung?
Bemerkung 2
Dieses Spiel hat durchaus Anwendungen, insbesondere wenn man auch andere Wahrscheinlichkeiten zuläßt. Man stelle sich z.B. die Zustände als Stundenpläne vor. Von Stundenplan A kann man nach Stundenplan B durch irgendeine kleine Änderung kommen (repraesentiert durch eine gerichtete Kante). Jeder Stundenplan hat ein Gewicht, das angibt, wie gut er ist. Ziel ist es, einen möglichst guten Stundenplan zu finden. Die Kanten sind mit bestimmten Wahrscheinlichkeiten versehen, die dazu führen sollen, die wenigen guten Stundenpläne, die es gibt, zu finden. Die Anzahl aller Stundenplaene sind so groß, dass man nicht den gesamten Graphen absuchen (geschweige denn im Rechner speichern) kann. Daher hat man immer nur einen kleinen Ausschnitt zur Verfügung und berechnet im nächsten Schritt die Nachbarschaft. Hinter dieser jetzt stark vereinfachten Darstellung stecken Markov-Ketten, Ergodensatz und lokale Suche.
Bemerkung 3
Wenn fuer alle Zustaende A, B gilt:

kann man daraus Verbindungen zu den Kirchhoffschen Gesetzen aus der Physik ziehen. Kanten stellen gerade ein Kabel mit Widerstand dar und die Bewegung auf dem Graphen sind fliessende Elektronen. Wenn man lange braucht um von A nach B zu kommen, heisst das gerade, dass der Widerstand zwischen A und B sehr gross ist.

Bemerkung 4
Mit solchen Graphen (jetzt ohne Wahrscheinlichkeiten, aber Beschriftungen wie Z und K) kann man in der Informatik die Regulaere Sprachen erkennen, die sehr oft vorkommen. Jedoch heissen diese Graphen dort endliche Automaten.

Das Münzwurfproblem im Internet

Das Münzwurfproblem zählt schon zu den klassischen Problemen der Wahrscheinlichkeitsrechnung. Im Internet findet man zum Coin Tossing Problem einigen Seiten z.B. :
  http://plus.maths.org/issue4/puzzle/coins/
  http://mathworld.wolfram.com/CoinTossing.html

Das Münzwurfproblem in Mathematica von R.Moebs

Im folgenden wird eine Programmsequenz in Mathematica gezeigt, mit die Erwartungswerte für einen Münzwurf 1 < n < 5 berechnet werden.
  kk = 5;
  Do[
      Table[gl[i]= Sum[{a[m] * k[m]^i},{m,1,n}]== Max[1, 2^{i-2}], {i,1,n}]
 
      SOL = Simplify[Solve[Table[gl[i], {i,1,n}], Table[a[i], {i,1,n }]]];
 
      Table[ a[i] = Replace[a[i], SOL[[1,i]]], {i,1,n } ];
 
      ERWWERT} = Sum[ (j+(n-1)) / 2^{j+(n-1)} *
                 Sum[ a[m] * k[m]^j, {m, 1, n}], {j, 1, infty} ];
 
      FPoly = {\#1}^n - Sum[ {\#1}^k, {k, 0, n-1} ];
 
      Table[ k[i] = Root[FPoly, i], {i, 1, n} ];
 
      EW[n] = Simplify[ERWWERT];
 
      Clear[a, k, gl, SOL, FPoly], {n, 1, kk }
    ]
 
  Table[EW[n], {n, 1, kk} ] -> {2,6,14,30,62}