Geburtstagsparadoxon – einfach erklärt

Kernidee

Das Geburtstagsparadoxon, auch Geburtstagsproblem genannt, zeigt, dass Wahrscheinlichkeiten oft falsch eingeschätzt werden. Die zentrale Aussage lautet: Befinden sich in einem Raum mindestens 23 Personen, dann ist die Chance, dass zwei oder mehr dieser Personen am gleichen Tag im Jahr Geburtstag haben, größer als 50 %. Der Jahrgang wird dabei nicht beachtet.

Paradox wirkt das Ergebnis, weil viele Menschen die Frage mit einer anderen verwechseln. Es geht nicht darum, ob eine bestimmte Person an einem bestimmten Tag Geburtstag hat oder ob jemand denselben Geburtstag wie eine vorher ausgewählte Person hat. Es geht darum, ob irgendein Paar aus der ganzen Gruppe an irgendeinem Tag denselben Geburtstag hat. Bei 50 Personen liegt diese Wahrscheinlichkeit sogar bei über 97 %.

Der wichtigste Grund ist die Zahl der möglichen Paare. Aus n Personen lassen sich n(n−1)/2 verschiedene Paare bilden. Bei 23 Personen sind das (23 über 2) = 253 Vergleiche. Schon ein einziges Paar mit gleichem Geburtstag genügt, damit das Ereignis eintritt. Mit jeder zusätzlichen Person wächst die Zahl der Paare um n und damit steigt auch die Wahrscheinlichkeit deutlich schneller, als viele intuitiv erwarten.

Annahmen und Grundformel

In der mathematischen Herleitung wird der 29. Februar vernachlässigt. Außerdem wird angenommen, dass die Geburtstage der n Personen unabhängige, identisch verteilte Zufallsvariablen sind und alle 365 Tage gleich wahrscheinlich sind. Diese Annahme entspricht einem Urnenmodell: Man zieht n Kugeln mit Zurücklegen aus einer Urne mit 365 Kugeln, die mit den Tagen von 1. Januar bis 31. Dezember beschriftet sind.

Die Berechnungen gelten für n ∈ {1,…,365}. Nach dem Schubfachprinzip ist bei mehr als 365 Personen sicher, dass mindestens zwei Personen am gleichen Tag Geburtstag haben, wenn der 29. Februar weggelassen wird. Wird der 29. Februar mitgezählt, gilt diese Sicherheit erst ab n > 366.

Die Anzahl aller möglichen Geburtstagsverteilungen für n Personen beträgt 365^n. Die Zahl der Verteilungen, bei denen alle Personen verschiedene Geburtstage haben, ist 365!/(365−n)! = 365 · 364 · … · (365−(n−1)). Deshalb ist die Wahrscheinlichkeit, dass alle n Personen unterschiedliche Geburtstage haben:

365! / (365^n · (365−n)!) = ∏_{k=0}^{n−1}(1 − k/365).

Die gesuchte Wahrscheinlichkeit, dass mindestens zwei Personen am gleichen Tag Geburtstag haben, ist die Gegenwahrscheinlichkeit:

P = 1 − ∏_{k=0}^{n−1}(1 − k/365).

Für n = 23 ergibt sich:

1 − (365 · 364 · … · 343) / 365^23 ≈ 0,5073 > 50 %.

Mit der Ungleichung 1−x < e^(−x) erhält man die Abschätzung P > 1 − e^(−n(n−1)/730). Daraus folgt für eine Wahrscheinlichkeit über 50 % die Bedingung n ≥ 23. Allgemein lautet die Abschätzung für d mögliche Tage und eine zu übertreffende Wahrscheinlichkeit p:

n > 1/2 + √(1/4 − 2d · ln(1−p)).

Bestimmter Tag statt beliebiges Paar

Eine andere Frage ist, wie wahrscheinlich es ist, dass mindestens eine Person an einem vorher festgelegten Tag Geburtstag hat. Diese Wahrscheinlichkeit ist viel kleiner als beim eigentlichen Geburtstagsparadoxon.

Ohne 29. Februar beträgt die Wahrscheinlichkeit für eine einzelne Person, an einem bestimmten Tag Geburtstag zu haben, 1/365 ≈ 0,27 %. Die Wahrscheinlichkeit, an diesem Tag nicht Geburtstag zu haben, ist q = 1 − 1/365 ≈ 99,73 %. Für n Personen ist die Wahrscheinlichkeit, dass mindestens eine Person an diesem bestimmten Tag Geburtstag hat:

P = 1 − q^n = 1 − (1 − 1/365)^n.

Um eine Wahrscheinlichkeit von 50 % zu erreichen, braucht man:

n ≥ ln(1−P) / ln(1−1/365).

Für P = 50 % ergibt sich:

n = ⌈ln(1/2) / ln(364/365)⌉ = 253.

Wenn der bestimmte Tag durch den Geburtstag einer anwesenden Person festgelegt ist, sind weitere 253 Personen, also insgesamt 254 Personen, nötig, um eine Wahrscheinlichkeit von 50 % zu erreichen. Anders als beim eigentlichen Geburtstagsparadoxon gibt es bei einem bestimmten Tag keine endliche Personenzahl, die Sicherheit garantiert: Für jede endliche Gruppe kann es sein, dass niemand an diesem ausgewählten Tag Geburtstag hat.

Sonderfälle und Verallgemeinerungen

In der Realität sind Geburtstage nicht völlig gleichmäßig über das Jahr verteilt; zum Beispiel werden im Sommer mehr Kinder geboren als im Winter. Dadurch steigt die Wahrscheinlichkeit, dass zwei Personen am selben Tag Geburtstag haben, leicht. Simulationen mit echten Daten zeigen aber weiterhin, dass die Wahrscheinlichkeit bei 23 Personen über 50 % liegt. Auch der vernachlässigte Schalttag ändert dieses Ergebnis nicht wesentlich.

Eine andere Fragestellung lautet: Wie wahrscheinlich ist es, dass genau zwei Personen am selben Tag Geburtstag haben und alle anderen an unterschiedlichen Tagen? Dafür gibt es 365 Möglichkeiten für den Tag des Doppelgeburtstags, (n über 2) Möglichkeiten für die beiden Personen und anschließend Verteilungen der übrigen n−2 Personen auf verschiedene andere Tage. Die Wahrscheinlichkeit ist:

(n über 2) · 365! / ((366−n)! · 365^n).

Diese Wahrscheinlichkeit wächst streng monoton bis n = 28 und beträgt dort rund 38,6 %. Danach fällt sie streng monoton. Ab n = 367 ist sie 0, weil dann das Ereignis „genau ein Doppelgeburtstag und sonst nur verschiedene Geburtstage“ nicht mehr eintreten kann.

Man kann auch fragen, wie groß eine Gruppe mindestens sein muss, damit mit mehr als 50 % Wahrscheinlichkeit mindestens m Personen am selben Tag Geburtstag haben. Für m = 2 braucht man 23 Personen, für m = 3 braucht man 88, für m = 4 braucht man 187, für m = 5 braucht man 313, für m = 6 braucht man 460, für m = 7 braucht man 623, für m = 8 braucht man 798, für m = 9 braucht man 985 und für m = 10 braucht man 1181 Personen.

Beispiele und Anwendungen

Ein anschauliches Beispiel erklärt den Unterschied zwischen den beiden Fragestellungen. Hat Peter am 19. Januar Geburtstag, dann beträgt die Wahrscheinlichkeit, dass ein bestimmter Freund ebenfalls am 19. Januar Geburtstag hat, 1/365. Bei mehreren ausgewählten Freunden wächst diese Wahrscheinlichkeit Schritt für Schritt um 1/365, wenn angenommen wird, dass die 365 Freunde alle unterschiedliche Geburtstage haben.

Beim eigentlichen Geburtstagsparadoxon ist aber nicht Peters bestimmter Geburtstag entscheidend. Es wird gefragt, ob beliebige Personen in einem Raum an irgendeinem beliebigen Tag gemeinsam Geburtstag haben. Kommt eine neue Person hinzu, kann sie mit jeder bereits anwesenden Person ein passendes Paar bilden. Deshalb steigt die Wahrscheinlichkeit viel schneller. Überschlagsrechnungen wie 1/365 + 2/365 + 3/365 zeigen diese Idee, sind aber etwas zu groß, weil sie mögliche bereits vorhandene Übereinstimmungen nicht vollständig berücksichtigen.

In der Kryptographie ist der Effekt wichtig bei Hashfunktionen. Eine kryptographische Hashfunktion soll aus einem Text einen Prüfwert erzeugen. Durch den Geburtstagseffekt ist es viel einfacher, zwei zufällige Texte zu finden, die denselben Prüfwert haben, als zu einem vorgegebenen Text einen weiteren Text mit demselben Prüfwert zu finden. Das steht im Zusammenhang mit dem Kollisionsangriff.

Eine verwandte Frage entsteht beim Spiel Memory. Dort liegen 2N Karten aus N Paaren verdeckt. Solange nur verschiedene Karten aufgedeckt werden, findet man ein Paar nur zufällig. Für N = 32 Paare ist bei 10 aufgedeckten Karten die Wahrscheinlichkeit größer als 50 %, mindestens ein Paar zu erhalten: 1 − P_32(10) ≈ 56,4 %. Für N = 50 liegt die Grenze bei 12 Karten, bei 183 Paaren bei 23 Karten und bei 365 Paaren bei 32 Karten.