Geburtstagsparadoxon

Das Geburtstagsparadoxon, manchmal auch als Geburtstagsproblem bezeichnet, ist ein Beispiel dafür, dass bestimmte Wahrscheinlichkeiten (und auch Zufälle) intuitiv häufig falsch abgeschätzt werden:

Befinden sich in einem Raum mindestens 23 Personen, dann ist die Chance, dass zwei oder mehr dieser Personen am selben Tag (ohne Beachtung des Jahrganges) Geburtstag haben, größer als 50 %.^[1]

Zur falschen Einschätzung der Wahrscheinlichkeit kommt es, weil im Geburtstagsparadoxon danach gefragt wird, wie wahrscheinlich es ist, dass zwei Personen aus einer Gruppe an einem beliebigen Tag im Jahr Geburtstag haben. Fälschlicherweise wird das Problem oft interpretiert als "wie wahrscheinlich es ist, dass eine Person aus einer Gruppe an einem bestimmten Tag im Jahr Geburtstag hat" (z.B. Übereinstimmung mit dem Geburtstag einer anderen, zusätzlichen Person) und diese Wahrscheinlichkeit ist tatsächlich deutlich kleiner.

Es wird oft Richard von Mises zugeschrieben. Laut Donald Ervin Knuth ist dieser Ursprung nicht so sicher: Das Geburtstagsparadoxon wurde informell unter Mathematikern schon in den 1930er Jahren diskutiert, ein genauer Urheber lässt sich aber nicht ermitteln.^[2]

Eingrenzung

Das Ergebnis der Frage:

Wie hoch ist die Wahrscheinlichkeit, dass bei 23 Personen mindestens zwei von ihnen am selben Tag Geburtstag haben (ohne Beachtung des Jahrganges)?

ist für die meisten verblüffend und wird deshalb als paradox wahrgenommen. So schätzen die meisten Menschen die Wahrscheinlichkeit um eine Zehnerpotenz falsch ein. Sie liegt nicht zwischen 1 % und 5 % (wie zumeist geschätzt), sondern über 50 %; bei 50 Personen sogar bei über 97 %.

Im Unterschied dazu steht die Wahrscheinlichkeit, dass jemand an einem ganz bestimmten Tag (ohne Beachtung des Jahrgangs) Geburtstag hat: Wenn man sich zum Beispiel eine der 23 Personen nimmt und fordert, dass jemand mit genau dieser am selben Tag Geburtstag hat. Ist also durch den Geburtstag einer der anwesenden Personen der bestimmte Tag festgelegt, sind weitere 253 Personen (also insgesamt 254 Personen) notwendig, um eine Wahrscheinlichkeit von 50 % zu erreichen (siehe Binomialverteilung).

Der Grund für diesen großen Unterschied liegt darin, dass es bei n Personen n(n − 1) / 2 verschiedene Paare gibt, die am selben Tag Geburtstag haben könnten. Die Wahrscheinlichkeit für das Zusammentreffen beziehungsweise Kollidieren zweier Geburtstage steigt daher für kleine Werte von n ungefähr mit dem Quadrat der Anzahl n an.

Ungleichmäßig verteilte Geburtstage

In der Realität sind nicht alle Geburtstermine gleich wahrscheinlich, so werden z. B. im Sommer mehr Kinder geboren als im Winter.^[3] Dadurch nimmt die Wahrscheinlichkeit, dass zwei Personen am gleichen Tag Geburtstag haben, leicht zu.^[4][5] Simulationen zeigen allerdings, dass auch für echte Daten die Wahrscheinlichkeit, dass zwei Personen am gleichen Tag Geburtstag haben, nach wie vor bei 23 Personen 50 % übersteigt.^[6] Auch die Berücksichtigung des in der Herleitung vernachlässigten Schalttags ändert daran nichts.

Bedeutung in der Kryptographie

Dieser Effekt hat eine Bedeutung bei kryptographischen Hash-Funktionen, die einen eindeutigen Prüfwert aus einem Text ergeben sollen. Es ist dabei viel einfacher, zwei zufällige Texte zu finden, die denselben Prüfwert haben, als zu einem vorgegebenen Text einen weiteren zu finden, der denselben Prüfwert aufweist (siehe Geburtstagsangriff).

Mathematische Herleitungen

Im Folgenden wird der 29. Februar vernachlässigt und angenommen, dass die Geburtstage der n Personen unabhängig identisch verteilte Zufallsvariablen aus der diskreten Gleichverteilung auf der 365-elementigen Menge {1. Jan., 2. Jan., …, 31. Dez.} sind. Diese Annahme ist beispielsweise dann nicht erfüllt, wenn sich unter den n anwesenden Personen Zwillinge befinden.

Im Urnenmodell entspricht diese Annahme einer Ziehung von n Kugeln mit Zurücklegen aus einer Urne, die 365 Kugeln mit der Beschriftung „1. Januar“, „2. Januar“, bis „31. Dezember“ enthält.

Wahrscheinlichkeit, dass mindestens zwei Personen an einem Tag Geburtstag haben

Die Anzahl aller möglichen Fälle ist für n Personen m = 365ⁿ, wobei alle Fälle gleich wahrscheinlich sind. Zum Beispiel ergeben sich für zwei Personen 365² = 133225 mögliche Fälle von Geburtstagskombinationen.

p(n) = Wahrscheinlichkeit für mindestens einen doppelten Geburtstag
q(n) = Wahrscheinlichkeit, dass ein Geburtstag mit deinem zusammenfällt

Von diesen möglichen Fällen beinhalten

$u = 365 \cdot 364 \cdots (365-n+1)$

nur unterschiedliche Geburtstage. Für die erste Person kann der Geburtstag frei gewählt werden, für die zweite gibt es dann 364 Tage, an denen die erste nicht Geburtstag hat etc.

Damit ergibt sich nach der Formel von Laplace die Wahrscheinlichkeit von

$\frac{u}{m} = \frac{365 \cdot 364 \cdots (365-n+1)}{365^n},$

dass alle n Personen an unterschiedlichen Tagen Geburtstag haben.

Die Wahrscheinlichkeit für mindestens einen doppelten Geburtstag im Verlauf eines Jahres ist somit

$P=1-\frac{u}{m}=1-\frac{365 \cdot 364 \cdots (365-n+1)}{365^n}$

Für n = 23 ergibt sich:

$1 - \frac{365 \cdot 364 \cdots 343}{365^{23}} \approx 0{,}5073 > 0{,}5.$

Nach dem Schubfachprinzip ist für alle n > 365 die Wahrscheinlichkeit gleich 1, es gibt also mit Sicherheit zwei Personen mit gleichem Geburtstag.

Eine Approximation

Der Ausdruck für P kann weiter umgeformt werden:

$P = 1-\frac{u}{m} = 1-\frac{365!}{(365-n)!\cdot365^n} = 1-\frac{n!\cdot{365 \choose n}}{365^n}.$

Mit der Stirling-Formel lässt sich dies gut nähern zu

$P \approx 1 - \left(\frac{365}{365-n}\right)^{365.5 - n}\!\!\!\!\!\cdot\, e^{-n},$

was man leicht mit einem Taschenrechner auswerten kann.^[7]

Wahrscheinlichkeit für einen bestimmten Tag

Eine andere Fragestellung liegt vor, wenn man nicht nach beliebigen Übereinstimmungen der Geburtstage sucht, sondern nach Übereinstimmung mit einem fest ausgewählten Tag im Jahr.

Ignoriert man wie bisher den 29. Februar, so ist die Wahrscheinlichkeit für eine Person, an einem solchen bestimmten Tag Geburtstag zu haben, gleich 1/365 ≈ 0,27 %.

Die Wahrscheinlichkeit für das Gegenteil, also die Wahrscheinlichkeit, an einem bestimmten Tag nicht Geburtstag zu haben, ist damit

$q = 1-\frac 1 {365}\approx99{,}73\,\%.$

Bei zwei Personen ist die Wahrscheinlichkeit, dass an dem vorher ausgewählten Tag keine von beiden Geburtstag hat, gleich $q^2\,$ (wie bisher nehmen wir an, dass die Geburtstage der Personen unabhängig sind).

Dabei mindestens einen Treffer zu haben (mindestens eine Person von zweien hat an einem bestimmten Tag Geburtstag), ist wieder die Gegenwahrscheinlichkeit, also

$P = 1-q^2.\,$

So fortfahrend für größere Anzahlen von Personen erhält man: Die Wahrscheinlichkeit P, dass mindestens eine Person von n anwesenden Personen an einem bestimmten Tag Geburtstag hat, ist

$P = 1-q^n.\,$

Damit lässt sich ausrechnen, wie viele Personen n man braucht, um eine bestimmte Wahrscheinlichkeit P zu erreichen, dass mindestens eine Person an einem bestimmten Tag Geburtstag hat:

$\left(1-\frac 1 {365}\right)^n = 1-P$

$\Leftrightarrow n = \frac{\ln(1-P)}{\ln(1-\frac 1 {365})}.$

Für eine Wahrscheinlichkeit von 50 % benötigt man

$n \ge \frac{\ln(\frac 1 2)}{\ln(\frac{364}{365})} \approx 253\,$ Personen.

Schließlich errechnet sich für den Fall, dass eine der n anwesenden Personen Geburtstag hat, die Wahrscheinlichkeit, dass von den übrigen n − 1 Personen mindestens eine am gleichen Tag Geburtstag hat, zu $1-q^{n-1}.\,$

Im Unterschied zur Wahrscheinlichkeit, dass mindestens zwei Personen an einem Tag Geburtstag haben (siehe oben), gibt es hier kein n, für das man eine sichere Aussage treffen kann: für jede Personenzahl gibt es die Möglichkeit, dass der ausgewählte Tag nicht als Geburtstag vorkommt (das Schubfachprinzip ist nicht anwendbar). Für alle n gilt: $P = 1-q^n < 1.\,$

Verwandte Fragestellungen

Bei dem Spiel Memory sind die Paare unter 2N Karten (bestehend aus N Paaren) aufzudecken. Zu Beginn des Spiels liegen alle Karten verdeckt und solange nur verschiedene Karten aufgedeckt werden, haben die Spieler keine Möglichkeit, ein Paar zu finden. Deshalb stellt sich die Frage – ähnlich wie beim Geburtstagsparadoxon – wie viele Karten man aufdecken muss, um mit einer gewissen Wahrscheinlichkeit (z.B. 50 %) mindestens ein Paar zu bekommen.

Die Anzahl N der verschiedenen Motive entspricht hier der Anzahl der Tage im Jahr (365) im Geburtstagsparadoxon. Üblicherweise wird Memory mit 32 Paaren gespielt, es gibt aber auch Varianten, so dass es sinnvoll ist, die Zahl N variabel zu halten.

Setzt man $P^\text{Mem}_N(n)$ für die Wahrscheinlichkeit, durch Aufdecken von n Karten nur verschiedene Karten aufzudecken, so gilt:

$P^\text{Mem}_N(n) = \frac{2N}{2N}\cdot\frac{2(N-1)}{2N-1}\cdot\frac{2(N-2)}{2N-2}\cdots \frac{2(N-n+1)}{2N-n+1}.$

Als Ergebnis bekommt man für N = 32: bei Aufdecken von 10 Karten ist die Wahrscheinlichkeit größer als 50 %, mindestens ein Paar zu erhalten (1 - P₃₂(10) = 56,4 %). Für N = 50 liegt die Grenze bei 12 Karten. Bei einem hypothetischen Memory mit 183 Paaren muss man 23 Karten aufdecken, bei 365 Paaren sind 32 Karten notwendig.^[8]

Dieses Ergebnis hat wichtige praktische Auswirkungen auf das Spiel, da die Spieler die Lust verlieren würden, wenn es zu lange dauert, bis das erste Paar aufgedeckt wird.

Siehe auch

• Das Sammelbilderproblem behandelt eine ähnliche Frage. Hier geht es – übertragen auf die Beobachtung von Geburtstagen in einer Gruppe von Menschen – darum, wie viele Personen ausgewählt werden müssen, damit jeder Tag des Jahres als Geburtstag einer der Personen vorkommt.
• Auch das Lincoln-Kennedy-Mysterium ist ein Phänomen, das mit der Übereinstimmung von biographischen Daten zu tun hat.

Einzelnachweise

1. ↑ Richard von Mises: Über Aufteilungs- und Besetzungswahrscheinlichkeiten Revue de la Faculté de Sciences de l'Université d'Istanbul N.S.4. 1938-39, S. 145-63
2. ↑ Donald E. Knuth: The Art of Computer Programming, Volume 3, Sorting and Searching. Second Edition, ISBN 0-201-89685-0. S. 513.
3. ↑ Emma Hawe, Alison Macfarlane and John Bithell: Daily and seasonal variation in live births, stillbirths and infant mortality in England and Wales, 1979–96 in Health Statistics Quarterly 9 Spring 2001 S 7: There was a clear seasonal pattern in the number of daily live births throughout the entire period, with lower numbers of births in the winter than the summer months.
4. ↑ Bloom, D. (1973), A birthday problem, American Mathematical Monthly, vol. 80, S. 1141–1142 enthält einen Beweis mit Lagrange-Multiplikatoren, dass für nicht gleichmäßig verteilte Geburtstage die Wahrscheinlichkeit zunimmt, dass zwei Personen am selben Tag Geburtstag haben.
5. ↑ Stefan Kirchner in de.sci.mathematik, 3. Nov. 2005
6. ↑ Hugo Pfoertner in de.sci.mathematik, 22. Jan. 2005
7. ↑ Es gibt weitere Approximationsmöglichkeiten, die hier noch eingefügt werden können. Entsprechend kann man die Güte der Approximationen angeben.
8. ↑ Dass man bei 183 (≈ 365/2) die gleiche Zahl n = 23 bekommt wie beim Geburtstagsparadoxon, ist kein Zufall: die Produktdarstellung für die Wahrscheinlichkeit zeigt (zumindest für die ersten Faktoren) eine große Ähnlichkeit.

Weblinks

 Wiktionary: Geburtstagsparadoxon – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

• http://www.im-chaos-daheim.de/geburtstag.php: Ein Applet zum Berechnen der Wahrscheinlichkeiten