© Wavebreak Media Ltd 123RF

Dass auf einer Geburtstagsparty mit 23 Gästen in mehr als 50 Prozent der Fälle zwei Gäste mit dem gleichen Geburtstag weilen sollen, hört sich für Mathe-Laien abenteuerlich an. Mit statistischen Bordmitteln macht sich Partylöwe Mike Schilli daran, die Behauptung zu beweisen.

Bei dem Problem kommt es auf die genaue Formulierung an. Niemand kann erwarten, auf eine Party mit 23 Leuten zu gehen und dort mit 50 Prozent Wahrscheinlichkeit jemanden mit dem gleichen Geburtsdatum zu treffen. Das unerwartete Ergebnis kommt dadurch zustande, dass sich n Gäste untereinander vergleichen, also jeder mit jeweils n-1 anderen Gästen. Dass so ein Paar zustande kommt, das im gleichen Monat und am gleichen Tag (der Jahrgang bleibt unberücksichtigt) Geburtstag hat, ist viel wahrscheinlicher, als wenn man nur seinen eigenen Geburtstag mit dem von n-1 Gästen vergleicht.

Von hinten aufgezäumt

Wie hoch ist die Wahrscheinlichkeit, dass auf einer Party mit nur zwei Gästen beide am gleichen Tag Geburtstag feiern? Mit einem zur Vereinfachung als 365 Tage lang angenommenen Jahr, ohne Berücksichtigung von saisonalen Geburtsschwankungen oder Spezialfällen wie Zwillingspartys, tritt dies in einem von 365 Fällen auf. Umgekehrt beträgt die Wahrscheinlichkeit, dass beide Gäste an unterschiedlichen Tagen Geburtstag haben, 364 zu 365.

Gesellt sich nun zu dem Pärchen ein weiterer Gast hinzu, setzt sich die Wahrscheinlichkeit, dass niemand im Raum am gleichen Tag Geburtstag feiert, aus dem Zusammentreffen zweier voneinander unabhängiger Ereignisse zusammen: Aus dem ersten Ereignis der vorhergehenden Runde mit der Wahrscheinlichkeit 364/365 und einem zweiten, nämlich dass die hinzugekommene Person weder mit der ersten noch der zweiten Person Geburtstag hat, also nur an 363 von 365 Tagen Geburtstag feiern kann.

Die Gesamtwahrscheinlichkeit verschiedener Geburtstage von drei Personen ermittelt der Statistiker durch Multiplikation der Wahrscheinlichkeiten der voneinander unabhängigen Einzelereignisse, also »364/365 * 363/365«, oder etwa »0,991795«. Das umgekehrte Ereignis, also der Fall, dass zwei oder mehr Personen am selben Tag Geburtstag feiern (Abbildung 1), ergibt sich mit einer Wahrscheinlichkeit von »1 – 0,991795«, also »0,008205«.

Abbildung 1: Auf einer Party mit 23 Leuten besteht eine Wahrscheinlichkeit von über 50 Prozent dass zwei Gäste den gleichen Geburtstag haben. Quelle: rawpixel, 123rf

So setzt sich die Reihe mit Gast Nummer vier, fünf und so weiter fort, und in jeder Runde reduziert sich die Anzahl der verbleibenden Tage und damit der Zähler der Division um den Wert eins, deren Ergebnis zur Wahrscheinlichkeit der letzten Runde hinzumultipliziert wird.

Listing 1 zeigt eine schlanke Python-Implementierung der Berechnung. In der Ausgabe (Abbildung 2) zeigt sich, dass beim 23. Gast die 50-Prozent-Marke der Wahrscheinlichkeit einer Geburtstagsdublette mit 50,73 Prozent überschritten wurde. Dabei setzt das Skript die Anzahl der im Kalender verbleibenden Tage anfangs auf 365 und zieht nach jeder Runde den Wert eins davon ab, da wieder ein Gast mit einem noch nicht gesehenen Geburtstag erschienen ist. Die Wahrscheinlichkeit »prob« gibt an, wie die Chancen stehen, dass keiner im Raum mit einem anderen den Geburtstag teilt: Bei einem Raum mit nur einer Person ist dies »1«, bei zweien »0,9973«.

01 #!/usr/bin/env python3
02
03 dates      = 365
04 dates_left = dates
05 prob       = 1
06
07 for person in range(1,24):
08   prob=prob*dates_left/dates
09   print("%2d: %.4f" % (person, 1-prob))
10   dates_left -= 1

Abbildung 2: Wahrscheinlichkeit einer Dublette.

In jeder Schleifenrunde multipliziert Listing 1 die Wahrscheinlichkeit der letzten Runde in »prob« mit dem hinzugekommenen Wahrscheinlichkeitswert und weist das Ergebnis wieder »prob« zu. Gewünscht wird jedoch nicht die Wahrscheinlichkeit keiner Geburtstagskollision, sondern das Gegenteil, die Chance auf ein Zusammentreffen, deshalb gibt Zeile 9 zur aktuellen Gästezahl jeweils die Wahrscheinlichkeit des gegenteiligen Ereignisses an, also »1-prob« für die Chance auf eines oder mehrere Geburtstagspaare auf der Party.

Simulant

Ob die Formel für die Berechnung richtig war, soll ein Simulationsskript (Listing 2)zeigen, das pro Runde 23 Gäste in der Liste »guest_bdays« einer Party zuordnet, jedem von ihnen aus 365 Integerwerten einen zufälligen Geburtstag zuweist und dann in der Funktion »bday_match()« aussortiert, ob in »guest_bdays« Integer-Duplikate vorliegen. Die Funktion »randint()« aus dem Modul »random« spuckt für die Geburtstage Werte zwischen den Extremen 1 und 365 (einschließlich) aus (Abbildung 3).

01 #!/usr/bin/env python3
02
03 import random
04
05 def bday_match(bdays):
06   seen = set()
07   for bday in bdays:
08     if bday in seen:
09       return True
10     seen.add(bday)
11   return False
12
13 for epoch in range(10):
14   parties    = 100000
15   matches    = 0
16   nof_days   = 365
17   nof_guests = 23
18
19   for party in range(parties+1):
20     guest_bdays=[]
21     for _ in range(nof_guests):
22       bday = random.randint(1,nof_days)
23       guest_bdays.append(bday)
24
25     if bday_match(guest_bdays):
26       matches += 1
27
28   print(matches/parties)

Die For-Schleife ab Zeile 13 iteriert dazu über insgesamt zehn Testläufe mit jeweils 100 000 Partys, und zu jeder Veranstaltung, bei der ein Geburtstagspaar auftritt, erhöht sich der Zähler »matches« um 1. Am Ende jedes Durchlaufs druckt das Skript den Quotienten aus der Anzahl der Partys mit Geburtstagspaaren zur Gesamtzahl der Partys aus, Abbildung 3 zeigt, dass sich der Wert bei etwa 50,7 Prozent einpendelt.

Abbildung 3: Das Simulationsskript mit 23 Personen schießt sich auf etwa 50 Prozent Überlappungswahrscheinlichkeit ein.

Die Funktion »bday_match()« ab Zeile 5 nimmt eine Python-Liste mit Integern entgegen und prüft, ob sich darin ein oder mehrere Duplikate befinden. Effizient geht dieser Test, indem die Funktion bereits gesehene Werte in einem Set »seen« mit einer Hash-Funktion häckselt, weil sie dann bei jedem neu untersuchten Wert blitzschnell nachsehen kann, ob der Wert schon im Set ist. Wer diese Aufgabe schon einmal bei einem Einstellungstest bekam, weiß, dass die Rechenzeit der Duplikatsprüfung mit diesem Verfahren bei n Listenelementen auf O(n) absinkt, während sie bei einer weniger cleveren Zwei-Schleifen-Lösung O(n  2) betrüge.

Schwarz auf weiß

Wie entwickelt sich der Wert für die Wahrscheinlichkeit einer Geburtstagskollision mit steigender Gästezahl? Dank der Python-Bibliothek »matplotlib«, einfach installiert mittels »pip3 install -user matplotlib«, produziert Listing 3 mit den Ausgabedaten von Listing 1 den Graphen in Abbildung 4:

01 #!/usr/bin/env python3
02
03 import matplotlib.pyplot as plt
04 import sys
05
06 x=[]
07 y=[]
08 for line in sys.stdin:
09   (guests,prob)=line.split(': ')
10   x.append(guests)
11   y.append(prob)
12
13 plt.plot(x,y)
14 plt.xlabel('Guests')
15 plt.ylabel('Probability')
16
17 plt.savefig('bd-collision.png')

./birthday-paradox | ./bd-plot

Mit dem speziellen File-Handle »sys.stdin« liest Listing 3 dabei die Ausgabezeilen von Listing 1 und spaltet sie mit der »split()«-Methode in Zeile 9 am Doppelpunkt, der Gästezahl und Wahrscheinlichkeit trennt. Für die x- und y-Werte im Graphen baut es die Listen »x« und »y« zusammen, indem es für jedes Wertepaar den neuesten Wert mit der »append()«-Methode an die jeweilige Liste anhängt. Die »plot()«-Methode nimmt dann alle x- und y-Werte gesammelt entgegen und zeichnet den Graphen, den die Methode »savefig()« in Zeile 17 in eine PNG-Bilddatei schreibt. Mit weniger Aufwand geht es kaum, und der Graph sieht ausgesprochen ansprechend aus.

Abbildung 4: Wahrscheinlichkeit gleicher Geburtstage bei mehr Gästen.

Was übrigens bei einer Party mit 100 Teilnehmern passiert, lässt sich ebenfalls mit den Skripten in dieser Ausgabe ermitteln: Zu 99,99996928 Prozent tanzt dort ein Geburtstagspaar, die Chance, dass bei dieser Megaparty alle Gäste unterschiedliche Geburtstage haben, beträgt mehr als eins zu drei Millionen.