Geburtstagsproblem
aus Wikipedia, der freien Enzyklopädie
Als Geburtstagsproblem (manchmal auch Geburtstagsparadoxon) wird die Tatsache bezeichnet, dass von 23 willkürlich ausgewählten Personen (zum Beispiel zwei Fußballmannschaften plus Schiedsrichter) mit einer Wahrscheinlichkeit von mehr als 50 % mindestens zwei am selben Tag Geburtstag haben. Welcher Tag das ist, spielt dabei keine Rolle.
Im Gegensatz dazu steht die Wahrscheinlichkeit, dass jemand an einem ganz bestimmten Tag Geburtstag hat – wenn man sich zum Beispiel den Schiedsrichter nimmt und fordert, dass jemand mit genau ihm am selben Tag Geburtstag hat. Für diesen Fall sind 253 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 
verschiedene Paare gibt, die am selben Tag Geburtstag haben könnten. Die Wahrscheinlichkeit für das Zusammentreffen beziehungsweise Kollidieren zweier Geburtstage steigt daher ungefähr mit dem Quadrat der Anzahl n an.
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 den selben Prüfwert haben, als zu einem vorgegebenen Text einen weiteren zu finden, der den selben Prüfwert aufweist (siehe Geburtstagsangriff).
Inhaltsverzeichnis |
[Bearbeiten] Mathematische Herleitungen
[Bearbeiten] Wahrscheinlichkeit für einen bestimmten Tag
Vernachlässigt man Schaltjahre und nimmt man an, dass alle Geburtstermine gleich wahrscheinlich sind, so ist die Wahrscheinlichkeit, an einem bestimmten Tag Geburtstag zu haben:
Da die Wahrscheinlichkeit für das Gegenteil (es gibt keine zwei Leute, die am selben Tag Geburtstag haben) unter einem bestimmten Schwellwert (in diesem Fall 50 %) liegen soll, muss über das Gegenereignis gerechnet werden. Die Wahrscheinlichkeit, an einem bestimmten Tag nicht Geburtstag zu haben, ist
.
Bei zwei unabhängigen Versuchen (die Geburtstage zweier Personen werden als unabhängig betrachtet) ist die Wahrscheinlichkeit, keinen Treffer zu haben (am bestimmten Tag hat keiner von beiden Geburtstag): Q = q2
Dabei mindestens einen Treffer zu haben (mindestens eine Person von zweien hat an einem bestimmten Tag Geburtstag), ist wieder die Gegenwahrscheinlichkeit, also: P = 1 − q2
Allgemein ausgedrückt ist die Wahrscheinlichkeit P, mit der mindestens eine Person von n anwesenden Personen an einem bestimmten Tag Geburtstag hat:
Damit lässt sich ausrechnen, wie viele Personen n 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:
Teilnehmer
[Bearbeiten] Wahrscheinlichkeit, dass zwei Personen an einem Tag Geburtstag haben
Die Anzahl aller möglichen Fälle ist für n Personen m = 365n. Zum Beispiel ergeben sich für zwei Personen 3652 = 133225 mögliche Kombinationen von Geburtstagen.
Weiterhin ist die Anzahl der Fälle, in denen nur unterschiedliche Geburtstage vorkommen,
.
Die erste Person kann den Geburtstag frei wählen, für die zweite gibt es dann 364 Tage, an denen die erste nicht Geburtstag hat.
Damit ergibt sich die Wahrscheinlichkeit von
dass alle n Personen an unterschiedlichen Tagen Geburtstag haben.
Die Wahrscheinlichkeit für mindestens einen doppelten Geburtstag ist somit
Berechnet man etwa für n=10, 11, …, bis 23 mit einem Taschenrechner P nach der oben angegebenen Formel kommt man zu dem Ergebnis, dass für eine Wahrscheinlichkeit von mindestens 50 % nur 23 Personen benötigt werden. In Gruppen größer als 57 Personen beträgt die Wahrscheinlichkeit schon über 99%.
Siehe auch: Lincoln-Kennedy-Mysterium
[Bearbeiten] Kleines Programm
Für die Wahrscheinlichkeit q(n) = 1 − P(n), dass bei n Personen keine übereinstimmenden Geburtstage auftreten gilt die Rekursion
.
Das folgende kleine C-Programm verwendet diese Rekursionsformel zur Berechnung der Wahrscheinlichkeiten P(n) für n = 1, 2, 3, … bis die Abbruchsbedingung 
erfüllt ist.
#include <stdio.h>
int main ( )
{
int n=1;
double q=1;
while ( q >= 0.5 )
{
q *= ( 365 - n + 1 ) / ( double ) 365;
n ++;
printf ( "n=%d P=%f\n", n-1, 1-q );
}
return 0;
}
[Bearbeiten] 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 [1]. Es lässt sich aber zeigen, dass für nicht gleichmäßig verteilte Geburtstage die Wahrscheinlichkeit zunimmt, dass zwei Personen am gleichen Tag Geburtstag haben[2][3]. In der Realität spielt die Abweichung von der Gleichverteilung keine besondere Rolle; Simulationen zeigen, dass auch für echte Daten die Wahrscheinlichkeiten, dass zwei Personen am gleichen Tag Geburtstag haben, nach wie vor bei 23 Personen 50 % übersteigt [4].
Ebenso ist die Vernachlässigung des Schalttages in der Herleitung kein Problem; würde man statt mit 365 mit 366 Tagen rechnen, erhält man dasselbe Ergebnis (ab 23 Personen eine Wahrscheinlichkeit größer 0,5). Dass der Schalttag nur alle vier Jahre auftritt, führt dann zu der oben erwähnten ungleichen Verteilung der Geburtstage.
[Bearbeiten] Quellen
- ↑ 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.
- ↑ Blom, D. (1973), A birthday problem, American Mathematical Monthly, vol. 80, pp. 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. Nov. 2005
- ↑ Hugo Pfoertner in de.sci.mathematik, 22. Jan. 2005
