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