Beweis des Birthday-Paradox

Für die Darstellung werden mathematischen Symbole mittels Latex verwendet

Zum Ansehen (in einem neuen Fenster) bitte den entsprechenden Link mit der linken Maustaste anklicken, zum Download bitte die rechte Maustaste benutzen.

Falls der Browser diese Darstellung nicht unterstützt, kann der Beweis auch als PDF-Datei (siehe unten) heruntergeladen werden.

Seien \(r_1, r_2, \ldots, r_n \in \{1, \ldots, B\} \) unabhängig, identisch verteilte Integer, dann gilt: \(n \approx \sqrt{2 \cdot ln 2} \cdot \sqrt{B} \approx 1,18 \cdot \sqrt{B} \Rightarrow P[\exists i\ne j: r_i=r_j] \ge 0,5 \)

Beweis:
OBdA seien die \(r_i\) gleichmäßig unabhängig (ungünstigster Fall)

\(P[\exists i\ne j: r_i=r_j] = 1-P[\forall i\ne j: r_i\ne r_j] = \)
\(= 1 -\bigg(\frac{B-1}{B}\bigg)\bigg(\frac{B-2}{B}\bigg)\ldots \bigg(\frac{B-n+1}{B}\bigg) = \)
\(= 1 - \prod_{i=1}^{n-1}\bigg(1-\frac{i}{B}\bigg)\), wg. \((e^{-x} = 1-\frac{x}{1!}+\frac{x^2}{2!}-\frac{x^3}{3!}\ldots \ge 1-x \ für \ x \ge 0 ) \ge\)
\(\ge 1 - \prod_{i=1}^{n-1} e^{-\frac{i}{B}} = 1 - e^{-\frac{1}{B}\sum_{i=1}^{n-1}i} \ge\)
\(\ge 1 - e^{-\frac{n^{2}}{2B}} \approx 1-e^{-\frac{1,18^{2}}{2}} \approx 1-e^{-0,72} > 0,5 \)

qed


Beispiel:
Wieviele Personen reichen, um mit 50%iger Wahrscheinlichkeit zu erreichen, dass zwei Personen am gleichen Tag Geburtstag haben?
Für \(\#(Personen) \approx 1,18 \cdot \sqrt{365} \approx 23 \) gilt:
\(P[\exists Person_i \ne Person_j : Geburtstag_i = Geburtstag_j] > 0,5 \)

Anmerkung: Die Geburtstage sind zwar nicht gleichverteilt, die Angabe stimmt aber „erst recht“.


Birthday-Paradox.pdf

Letzte Änderung: 2016-01-05