Das Geburtstagsparadoxon, manchmal auch als Geburtstagsproblem bezeichnet, ist ein Beispiel dafür, dass bestimmte Wahrscheinlichkeiten (und auch Zufälle) intuitiv häufig falsch geschätzt werden, beispielsweise liegt die tatsächliche Zahl von 23 Personen meist unterhalb der intuitiven Schätzung:
Zum falschen Schätzen der Wahrscheinlichkeit kommt es, weil im Geburtstagsparadoxon danach gefragt wird, wie wahrscheinlich es ist, dass zwei beliebige Personen aus einer Gruppe an ein und demselben beliebigen Tag im Jahr Geburtstag haben. Fälschlich wird das Problem oft interpretiert als „wie wahrscheinlich es ist, dass eine bestimmte Person aus einer Gruppe an einem bestimmten Tag im Jahr Geburtstag hat“ (z. B. Übereinstimmung mit dem Geburtstag einer anderen Person der Gruppe), und diese Wahrscheinlichkeit ist tatsächlich deutlich kleiner.
Das Paradoxon ist Richard von Mises zugeschrieben worden, z. B. von Persi Diaconis und Frederick Mosteller.P. Diaconis, F. Mosteller: Methods for Studying Coincidences. In: Journal of the American Statistical Association. 84, 4, S. 853–861. Donald E. Knuth schrieb 1973, Mathematiker hätten das Geburtstagsparadoxon schon in den 1930er Jahren diskutiert; der Urheber sei unbekannt.Donald E. Knuth: The Art of Computer Programming. Bd. 3: Sorting and Searching. zweite Auflage, ISBN 0-201-89685-0. S. 513.
Eingrenzung Frage: Wie hoch ist die Wahrscheinlichkeit, dass bei 23 Personen mindestens zwei am selben Tag im Jahr Geburtstag haben?
Die Antwort ist für die meisten Menschen verblüffend und wird als paradox wahrgenommen. Die meisten Menschen, die sich dafür interessieren, schätzen die Wahrscheinlichkeit um eine Zehnerpotenz falsch ein. Sie liegt nicht (wie zumeist geschätzt) zwischen 1 % und 5 %, sondern über 50 %, bei 50 Personen sogar bei über 97 %.
Im Unterschied dazu steht die Wahrscheinlichkeit, dass jemand an einem bestimmten Tag (ohne Beachtung des Jahrgangs) Geburtstag hat: Ist 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 den Artikel Binomialverteilung – Gemeinsamer Geburtstag im Jahr und weiter unten den Abschnitt Wahrscheinlichkeit für einen bestimmten Tag).
Der Grund für diesen großen Unterschied liegt darin, dass aus Personen verschiedene Paare gebildet werden können; die Zahl der möglichen Paare steigt daher mit wachsender Zahl der Personen in der Gruppe immer schneller an – wenn die te Person dazukommt, steigt die Zahl der Paare um . Die Bedingung für das in Frage stehende Ereignis ist schon erfüllt, wenn ein einziges dieser Paare am selben Tag Geburtstag hat. Da die Wahrscheinlichkeit, am selben Tag Geburtstag zu haben, für jedes Paar gleich groß ist und die Anzahl der Paare mit wachsender Zahl an Personen immer schneller ansteigt, steigt auch die Wahrscheinlichkeit, dass zwei Personen in der Gruppe am selben Tag Geburtstag haben, mit wachsender Gruppengröße deutlich schneller an als bei der Variante, wenn ein Geburtsdatum durch eine vorher bestimmte Person fixiert wird.
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.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: 9 Spring 2001 (PDF; 180 kB), 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.“ Dadurch nimmt die Wahrscheinlichkeit, dass zwei Personen am selben Tag Geburtstag haben, leicht zu.D. Bloom (1973): A birthday problem. American Mathematical Monthly, Bd. 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 gleichen Tag Geburtstag haben.Stefan Kirchner in de.sci.mathematik, 3. November 2005. Simulationen zeigen, dass auch für echte Daten die Wahrscheinlichkeit, dass zwei Personen am selben Tag Geburtstag haben, nach wie vor bei 23 Personen 50 % übersteigt.Hugo Pfoertner in de.sci.mathematik, 22. Januar 2005. 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 Hashfunktionen, 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 Kollisionsangriff).
Mathematische Herleitungen Im Folgenden wird der 29. Februar vernachlässigt und angenommen, dass die Geburtstage der Personen unabhängige, identisch verteilte Zufallsvariablen aus der diskreten Gleichverteilung auf der 365-elementigen Menge sind. Diese Annahme ist beispielsweise dann nicht erfüllt, wenn sich unter den anwesenden Personen Zwillinge befinden.
Im Urnenmodell entspricht diese Annahme einer Ziehung von Kugeln mit Zurücklegen aus einer Urne, die 365 Kugeln mit der Beschriftung „1. Januar“, „2. Januar“ usw. bis „31. Dezember“ enthält.
Alle folgenden Berechnungen gelten nur für die Beschränkung auf weniger als 366 Personen, also . Nach dem Schubfachprinzip ist (unter Vernachlässigung des 29. Februars) für alle die Wahrscheinlichkeit gleich 1, es gibt also mit Sicherheit zwei Personen mit gleichem Geburtstag. Wenn der 29. Februar als Geburtstag nicht vernachlässigt wird, dann gilt dies erst ab .
Wahrscheinlichkeit, dass mindestens zwei Personen am gleichen Tag Geburtstag haben mini|308x308px|Die rote Kurve zeigt die Wahrscheinlichkeit, dass mindestens zwei Personen am gleichen Tag Geburtstag haben. Die blaue Kurve zeigt die Wahrscheinlichkeit, dass alle Personen an verschiedenen Tagen Geburtstag haben. mini|308x308px|Die schwarze Kurve zeigt die exakte Wahrscheinlichkeit, dass mindestens zwei Personen am gleichen Tag Geburtstag haben (die angegebene Formel in der Legende ist aber die Gegenwahrscheinlichkeit). Die rote Kurve zeigt die Approximation . Die Anzahl aller möglichen Variationen ist für Personen , wobei alle Fälle gleich wahrscheinlich sind. Zum Beispiel ergeben sich für zwei Personen mögliche Fälle von Geburtstagsvariationen.
Von diesen möglichen Fällen beinhalten
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
dass alle Personen an unterschiedlichen Tagen Geburtstag haben.
Die Wahrscheinlichkeit für mindestens einen doppelten Geburtstag im Verlauf eines Jahres ist somit .
Mithilfe der Ungleichung der Exponentialfunktion für ergibt sich
.
Wenn diese Wahrscheinlichkeit größer als 50 % ist, folgt daraus:
Aus dieser quadratischen Ungleichung folgt . Weil eine ganze Zahl ist, gilt .
Die allgemeine Formel für diese Abschätzung lautet
,
wobei die Anzahl der Personen, die Anzahl der möglichen Tage und die zu übertreffende Wahrscheinlichkeit ist.
Für ergibt sich .
Eine Approximation
Der Ausdruck für kann weiter umgeformt werden:
Mit der Stirlingformel lässt sich dies gut nähern zu
was man leicht mit einem Taschenrechner auswerten kann.
In einer Gruppe von 23 Personen muss man verschiedene Vergleiche anstellen, um einen vollständigen Überblick zu bekommen, ob es gemeinsame Geburtstage gibt, und wenn ja, wie viele.
Wahrscheinlichkeit für einen bestimmten Tag mini|380px| = Wahrscheinlichkeit für mindestens einen doppelten Geburtstag = Wahrscheinlichkeit, dass mindestens ein Geburtstag mit deinem zusammenfällt Eine andere Frage 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
Die Wahrscheinlichkeit für das Gegenteil, also die Wahrscheinlichkeit, an einem bestimmten Tag nicht Geburtstag zu haben, ist damit
Bei zwei Personen ist die Wahrscheinlichkeit, dass an dem vorher ausgewählten Tag keine von beiden Geburtstag hat, gleich (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:
So fortfahrend für größere Anzahlen von Personen erhält man: Die Wahrscheinlichkeit , dass mindestens eine Person von anwesenden Personen an einem bestimmten Tag Geburtstag hat, ist
Damit lässt sich ausrechnen, wie viele Personen man braucht, um eine bestimmte Wahrscheinlichkeit zu erreichen, dass mindestens eine Person an einem bestimmten Tag Geburtstag hat:
Für eine Wahrscheinlichkeit von 50 % benötigt man
Personen, wobei die obere Gaußklammer bezeichnet. Wie beim vorigen Problem sind auch hier bei 253 Personen 253 Vergleiche mit dem bestimmten Datum erforderlich, um einen vollständigen Überblick über die Situation zu haben.
Allgemein gilt für eine Auswahl aus einem Zeitraum mit Tagen:
und
Schließlich errechnet sich für den Fall, dass eine der anwesenden Personen Geburtstag hat, die Wahrscheinlichkeit, dass von den übrigen Personen mindestens eine am gleichen Tag Geburtstag hat, zu .
Im Unterschied zur Wahrscheinlichkeit, dass mindestens zwei Personen an einem Tag Geburtstag haben (siehe oben), gibt es hier kein für das man eine sichere Aussage treffen kann: Für jede (endliche) Personenzahl besteht die Möglichkeit, dass der ausgewählte Tag nicht als Geburtstag vorkommt (das Schubfachprinzip ist nicht anwendbar). Für alle gilt .
Wahrscheinlichkeit, dass genau zwei Personen am selben Tag Geburtstag haben Bei diesem Problem lautet das konkrete Ereignis: „2 Personen haben am gleichen Tag Geburtstag, alle anderen an unterschiedlichen Tagen.“
Es gibt 365 Möglichkeiten für den Tag des Doppelgeburtstags. Die beiden Personen lassen sich auf Arten auswählen. Die verbleibenden Personen werden nacheinander auf die restlichen 364 Tage verteilt, und zwar so, dass es keine weitere Mehrfachbelegung gibt. Dafür gibt es Möglichkeiten. Danach bleiben noch Tage des Jahres übrig, an denen niemand Geburtstag hat. Insgesamt erhält man für das Eintreten des Ereignisses günstige Fälle. Die gesuchte Wahrscheinlichkeit für das Eintreten des Ereignisses beträgt , da wieder alle 365 Tage des Jahres als gleich wahrscheinlich angenommen werden.
Die Wahrscheinlichkeiten stellen eine Zahlenfolge in Abhängigkeit von dar, die streng monoton bis wächst. Dort beträgt die Wahrscheinlichkeit rund 38,6 %. Danach fällt die Folge streng monoton. Ab ist die Wahrscheinlichkeit 0, da das Ereignis in diesen Fällen nicht mehr eintreten kann, weil es dann Mehrfachgeburtstage oder mehrere Doppelgeburtstage gibt.
Mehr als zwei Personen mit gleichem Geburtstag Eine Verallgemeinerung der Fragestellung ist, aus wie vielen Personen eine Gruppe bestehen muss, damit die Wahrscheinlichkeit, dass mindestens Personen am selben Tag Geburtstag haben, größer als 50 % ist. Die folgende Tabelle zeigt die Mindestanzahl der Personen für : Mindestanzahl n von Personenmn223388418753136460762387989985101181
Beispielhafte Erläuterung zum Auftreten des scheinbaren Paradoxons Wie bei vielen Problemen der Kombinatorik und Wahrscheinlichkeit kommt es auch hier auf den genauen Kontext bzw. den Ablauf des Experimentes an. Denken wir uns folgende Experimente. Zur Vereinfachung habe ein Jahr immer exakt 365 Tage.
Eine bestimmte Person an einem bestimmten Tag