© natalimis 123RF

Kommt es wirklich vor, dass beim Münzwurf zehnmal hintereinander Kopf kommt? Oder beim Lotto die Zahlen von 1 bis 6? Michael Schilli forscht dem Gesetz der großen Zahlen nach.

Wer den Aktienmarkt verfolgt, hört auch so manchen Prahlhans damit hausieren gehen, dass seine Kauf- und Verkaufsstrategie angeblich nur Gewinne und niemals Verluste einfährt. Dabei weiß jeder, der “A Random Walk down Wall Street” [2] gelesen hat, dass wilde Aktienspekulation auf die Dauer nur in den Spielerbankrott führt. Aber was ist mit den wenigen Fondsmanagern, die ihre Einlagen seit 20 Jahren so verwalten, dass sie tatsächlich Jahr für Jahr mit Gewinnen punkten?

Laut [2] gäbe es selbst bei einem Münzwurf-Wettbewerb mit genügend Mitspielern eine kleine Anzahl meisterhafter Werfer, die zum bassen Erstaunen ihrer Mitstreiter anscheinend spielend 20 Mal hintereinander “Kopf” werfen, ohne dass jemals “Zahl” auftaucht. Aber wie wahrscheinlich ist das wirklich?

Kopf oder Zahl

Es lässt sich leicht errechnen, dass eine Zweierfolge derselben Münzseite mit der Wahrscheinlichkeit 0,5*0.5 (also 0,25) auftritt. Ein Hattrick kommt mit 0,53=0,125, und eine Zwanziger-Folge ist mit 0,520=0,000000954 schon recht unwahrscheinlich. Dennoch: Wenn ein Programm es nur oft genug probiert, klappt es auch irgendwann einmal, was ich heute auf die Probe stelle. Der kleine Python-Generator »coin_throw()« in Listing 1 simuliert Münzwürfe, bei denen mit jeweils 50 Prozent Wahrscheinlichkeit “Kopf” oder “Zahl” fallen.

01 #!/usr/bin/env python3
02 import random
03
04 def coin_throw():
05   sides=('heads', 'tails')
06
07   while True:
08     yield sides[random.randint(0, 1)]
09
10 def experiment():
11   run     = 1
12   max_run = 0
13   prev    = ""
14   count   = 0
15
16   for side in coin_throw():
17     count += 1
18
19     if prev == side:
20       run += 1
21       if run > max_run:
22         max_run = run
23         print("max_run: %d %s (%d)" %
24               (max_run, side, count))
25     else:
26       prev = side
27       run  = 1
28
29 experiment()

Listing 1 teilt sich in den Wurfgenerator »coin_throw()« und die Auswertung des Experiments in der Funktion »experiment()«. In eine For-Schleife wie in Zeile 16 eingebettet, sieht es so aus, als würde »coin_throw()« eine lange Liste von Ergebnisstrings aus »heads« oder »tails« zurückliefern, aber in Wirklichkeit handelt es sich bei der Funktion um einen dynamischen Generator, der immer dann einen neuen Wert liefert, wenn eine Iterationspumpe wie die For-Schleife nachfragt, ob noch mehr kommt.

Im Haus des Generators

Wie funktioniert der Generator, dessen Ausgabe in Abbildung 1 zu sehen ist? Der Schlüssel ist der »yield«-Befehl in Zeile 8 in Listing 1. Python unterbricht auf ein »yield« hin die Ausführung der aktuellen Funktion, merkt sich deren Zustand und gibt in Zeile 8 den ihr übergebenen Zufallswert (»heads« oder »tails«) zum aufrufenden Programm zurück. Dazu liefert die Methode »randint(0,1)« mit jeweils 50 Prozent Wahrscheinlichkeit die Integerwerte »0« oder »1«, mit denen das Skript jeweils einen der beiden Einträge im Tupel »sides« herauspickt.

Abbildung 1: Münzwurf per Python-Generator.

Beim nächsten Aufruf der Funktion »coin_throw()« kehrt der Programmfluss zum Ort des letzten Absprungs zurück, um dort weiterzumachen, wo »yield« vorher aufgehört hat. Im vorliegenden Fall ist das die Endlosschleife mit »while True« in Zeile 7, deren Bedingung auch weiterhin wahr ist, woraufhin ein weiterer »yield«-Befehl erneut einen Zufallswert zurückschickt. So produziert der Generator in »coin_throw()« eine endlose Folge von Werten und schiebt immer einen neuen nach, falls die »for«-Schleife nach mehr verlangt.

Der Restcode der Funktion »experiment()« merkt sich die Anzahl gleichartiger Würfe in »run«, die maximal längste Folge in »max_run«, den vorhergehenden Münzwurf in »prev« (»heads«, »tails«) und die Gesamtzahl der Würfe bisher in »count«.

Fatales Double Down

Die Ausgabe des Skripts in Abbildung 2 offenbart, dass nach 21 Millionen Durchgängen tatsächlich einmal eine Folge von 23 »tails« hintereinander aufgetreten ist. Hätte ein Spieler nach der Double-Down-Methode bei jedem Verlust jeweils den Einsatz fürs nächste Spiel verdoppelt, bräuchte er bei einem Anfangseinsatz von einem Euro insgesamt 223-1 = 8 388 607 Euro Spielkapital, um nicht bankrott zu gehen, falls er auf “heads” gesetzt hat und dummerweise 23-mal hintereinander »tails« kommt.

Abbildung 2: Längste Folgen von identischen Münzwürfen.

Ganz große Klasse

Python bietet aber nicht nur Generatoren mit dem »yield«-Schlüsselwort, auch Klassen können Generatoren als Iteratoren implementieren. Hierzu definiert der oder die Pythonista zwei Methoden: »__iter__()« und »__next__()«. Die “Dunder” genannten Quadrupel-Unterstriche kennzeichnen offizielle Eintrittspunkte für Pythons Standard-Library. Sieht der Python-Interpreter einen Schleifenkopf wie »for n in Roulette()«, instanziert er ein Objekt der Klasse »Roulette«, greift sich mit »__iter__()« dessen Iterator und holt dann von diesem mit Aufrufen von »__next__()« so lange neue Werte ab, bis der Iterator eine Exception wirft.

In der vorliegenden Klasse in Listing 2 gibt »__iter__()« bequemerweise gleich die »Roulette«-Instanz selbst zurück, denn die Klasse braucht keinen separaten Iterator, da sie ihn mit »__next__()« gleich selbst implementiert. Dessen Aufruf gibt immer wieder eine neue Zufallszahl im Bereich 0 bis 36 zurück und wirft niemals eine Exception, sodass der Fluss für die For-Schleife im Hauptprogramm niemals versiegt.

01 #!/usr/bin/env python3
02 import random
03
04 class Roulette:
05   slots   = 36
06   numbers = range(0,slots+1)
07
08   def __iter__(self):
09     return self
10
11   def __next__(self):
12     return self.__class__.numbers[random.randint(0, self.__class__.slots)]

Die Klasse »Roulette« definiert dazu zwei Klassenvariablen: »slots« als die höchste Zahl im Roulette-Kreisel und »numbers« als eine Sequenz von Nummern von 0 bis einschließlich 36. Es ist sinnvoll, die Variablen nur einmal für die Klasse zu definieren und nicht etwa pro Instanz oder sie gar bei jedem Aufruf des Operators zeitverschwenderisch neu aufzubauen.

Klasse oder Instanz?

Pythons Klassenvariablen unterscheiden sich von Instanzvariablen dadurch, dass der Zugriff auf sie nicht mit »self.variable«, sondern per »__class__.variable« oder »self.__class__.variable« erfolgt. Bei rein lesendem Zugriff könnte man die Klassenvariable sogar über den Instanzweg »self.variable« referenzieren.

Wer Letztere allerdings anschließend modifiziert, erlebt sein blaues Wunder, da Python hinterrücks eine neue Instanzvariable anlegt, die sich von der Klassenvariablen abgekoppelt hat, und anschließend jedes Objekt seine eigenen Werte erhält, statt etwaige Änderungen auf Klassenebene zu propagieren. Methoden finden die Klassenvariable auch nicht einfach über deren Namen, wer in »__iter__()« einfach »slots« referenziert, bekommt einen Syntaxfehler um die Ohren.

Wie so häufig in der Python-Welt gilt es auch hier, einen kleinen, aber feinen Unterschied zwischen den Versionen 2 und 3 zu beachten: Der Iterator-Einstieg in die Generatorklasse heißt in Python 2 »next« und nicht »__next__« wie in Python 3, sodass Programmierer, die beide Versionen bedienen wollen, typischerweise einfach eine weitere Methode »next()« definieren, die ihr übergebene Parameter unmodifiziert an »__next__()« weiterreicht. Python 3 nutzt kein »next()«, sodass der Kompatibilitätstrick dort keinen Schaden anrichtet.

Die Ausgabe der statistischen Auswertung des Roulette-Generators zeigt Listing 3. Nach 27 Durchgängen trat zum ersten Mal eine Dublette auf, die Zahl 11 kam zweimal hintereinander. Nach 6249-mal “Faites votre jeux” kam dann dreimal hintereinander die 15, nach 57 393 Spielen viermal die 34 und so weiter.

1 $ ./roulette
2 max_run: 2 11 (27)
3 max_run: 3 15 (6249)
4 max_run: 4 34 (57393)
5 max_run: 5 1 (3363284)
6 max_run: 6 0 (95846456)
7 max_run: 7 26 (357289507)

Tumultartige Szenen

Was wäre wohl in Las Vegas an einem Spieltisch los, an dem sechsmal hintereinander die Null käme wie in Listing 4 nach 95 Millionen Kreiseldurchgängen? Tumultartige Szenen würden sich im Casino wahrscheinlich abspielen, bevor der Pitboss erschiene und den Croupier in den Feierabend schickte, weil jeder Spieler am Tisch sofort vermuten würde, dass etwas nicht mit rechten Dingen zugeht. Doch statistisch gesehen läuft alles in geordneten Bahnen ab, irgendwann wiederholen sich auch Zufallswerte einfach zwangsläufig.

01 #!/usr/bin/env python3
02 import random
03
04 def lotto_draw():
05   total   = 49
06   draws   = 6
07   numbers = list(range(1,total+1))
08   size    = total
09   result  = []
10
11   for _ in range(draws):
12     idx = random.randrange(size)
13     result.append(numbers[idx])
14     numbers[idx] = numbers[size-1]
15     size -= 1
16
17   return sorted(result)
18
19 def is_consecutive(draw):
20   prev=-1
21   for number in draw:
22     if prev < 0:
23       prev=number
24     elif prev + 1 == number:
25       prev = number
26     else:
27       return False
28   return True
29
30 count = 0
31 while True:
32   count += 1
33   draw=lotto_draw()
34   if is_consecutive(draw):
35       print("%d: %s" % (count, str(draw)))
36       break

Tolles Lotto

Was dächten deutsche Fernsehzuschauer, falls die Lottofee die gezogenen Zahlen mit 1, 2, 3, 4, 5, und 6 ansagen würde? Da die Wahrscheinlichkeit für einen Sechser bei etwa 1:14 Millionen liegt und es 44 Kombinationen von direkt aufeinander folgenden Lotto-Zahlen-Kombinationen gibt (1, 2, 3, 4, 5, 6 bis 44, 45, 46, 47, 48, 49), liegt die Chance einer großen Straße beim Lotto bei etwa 1:318 000 – damit sollte sich das unglaubliche Ereignis mit einem schnellen Ziehungsgenerator relativ zügig einstellen.

Listing 4 zeigt einen Ziehungsautomaten in der Funktion »lotto_draw()«. Von 49 nummerierten Kugeln in der Liste »numbers« zieht er sechsmal eine zufällige und entfernt sie anschließend, um Doppelziehungen auszuschließen. Da es enorm Rechenzeit kostet, ein Element aus einer Python-Liste zu entfernen und die restlichen Elemente aufrücken zu lassen, um die Lücke zu schließen, vertauscht die Funktion den Wert des ausgewählten Elements kurzerhand mit dem letzten Element der Liste und setzt die Listenlänge »size« um eins herunter.

Zurück gibt »lotto_draw()« eine sortierte Liste mit sechs zufällig ausgewählten Kugeln. Das Hauptprogramm ab Zeile 30 prüft nun mittels »is_consecutive()«, ob die gezogenen Zahlen sich jeweils nur um eins von ihrem Vorgänger unterscheiden. Ist dies der Fall, druckt Zeile 35 die Anzahl der bislang durchgeführten Ziehungen in »count« aus sowie die Glückszahlen, die zum Abbruch führten. Abbildung 3 zeigt, dass dies manchmal schon nach 30 000 Durchgängen auftritt, manchmal aber erst bei mehr als 800 000 – eben zufällig, aber im Rahmen der errechneten Wahrscheinlichkeit.

Abbildung 3: Der Lotto-Generator ermittelt die Anzahl der Ziehungen, bis sich schließlich ein lustiges Ergebnis einstellt.

Zur Implementierung dieser und anderer cooler Python-Kunstgriffe sei das Buch “Python Tricks” von Dan Bader empfohlen [3]. Es zeigt eine Vielzahl von alltäglichen Programmieraufgaben, für die es elegante Lösungen in Python gibt. Es eignet sich hervorragend für Umsteiger aus anderen Programmiersprachen (wie Perl!), die sich hauptsächlich dafür interessieren, typische Idiome in sauberes Python umzusetzen, und nicht bei Adam und Eva und “Hello World” anfangen wollen.