Benutzer:Pardox/Spielwiese

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. Das Geburtstagsparadoxon wird oft Richard von Mises zugeschrieben:

Befinden sich in einem Raum mindestens 23 Personen, dann ist die Chance, dass zwei oder mehr dieser Personen am selben Tag Geburtstag haben, größer als 50%.

Laut Donald Ervin Knuth ist dieser Ursprung nicht so sicher: Das Geburtstagsparadoxon wurde informell unter Mathematikern in den 1930er Jahren diskutiert, ein genauer Urheber lässt sich aber nicht nachvollziehen.

Mathematische Herleitung

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 $\{{\mbox{1. Januar}},\ {\mbox{2. Januar}},\ \dots ,{\mbox{31. Dezember}}\}$ 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.

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

Von diesen möglichen Fällen beinhalten

$u=365\cdot 364\cdot \dots \cdot (365-n+1)={\frac {365!}{(365-n)!}}$

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!}{(365-n)!\cdot 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!}{(365-n)!\cdot 365^{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}$

Berechnet man etwa für $n$=10, 11, …, bis 23 mit einem Taschenrechner $P$ nach der oben angegebenen Formel für mindestens einen doppelten Geburtstag im Verlauf eines Jahres, kommt man zu dem Ergebnis, dass für eine Wahrscheinlichkeit von mindestens 50 % nur 23 Personen benötigt werden. In Gruppen ab 57 Personen beträgt die Wahrscheinlichkeit schon über 99 % (siehe Grafik).

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. Dadurch nimmt die Wahrscheinlichkeit, dass zwei Personen am gleichen Tag Geburtstag haben, leicht zu. 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. 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).

Variante des Geburtstagsparadoxons

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).

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

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.

Mathematische Herleitung

Unter den oben getroffenen Annahmen ist die Wahrscheinlichkeit, an einem bestimmten Tag Geburtstag zu haben

$P={1 \over 365}\approx 0{,}27\ \%$.

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

$q=1-{1 \over 365}\approx 99{,}73\ \%$.

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=q^{2}$.

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}\,$.

Allgemein ausgedrückt ist die Wahrscheinlichkeit $P$, mit der mindestens eine Person von $n$ anwesenden Personen an einem bestimmten Tag Geburtstag hat

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

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.

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

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

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

$n\geq {{\ln({1 \over 2})} \over {\ln({364 \over 365})}}\approx 253$ Teilnehmer.

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

$Q=1-\left(1-{1 \over 365}\right)^{n-1}$.

Die Wahrscheinlichkeit $Q$ ist gleichzeitig der adäquate Vergleichsmaßstab, wenn im Gegensatz zu den Betrachtungen für einen bestimmten Tag der Fokus auf die Gesamtheit aller Tage des Jahres gerichtet wird.

Siehe auch

Auch das Lincoln-Kennedy-Mysterium ist ein Phänomen, das mit der Übereinstimmung von biographischen Daten zu tun hat.

Weblinks

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