Seite 1 von 1

Herleitung Geburtstagsproblem/Hashkollisionen

Verfasst: 8. Feb 2013 14:52
von arne.lottmann
In der Vorlesung wurde die Formel zur Abschätzung der benötigten Anzahl von Menschen für einen doppelten Geburtstag so hergeleitet:
\(q = \prod\limits_{i=1}^{k-1} (1 - \frac{i}{m})\)
\(q \leq \prod\limits_{i=1}^{k-1} e^{-\frac{i}{m}} = e^{-\sum\limits_{i=1}^{k-1} \frac{i}{m}} = e^{-\frac{k(k-1)}{2m}}\)
\(\Rightarrow k \geq (1 + \sqrt{1 + 8m \log(2)}) / 2\)

Kann jemand die fehlenden Schritte zwischen der vorletzten und der letzten Zeile ergänzen? In meinen Versuchen bin ich immer auf folgendes gekommen:
\(k \leq (1 + \sqrt{1 + 8m \log(2)}) / 2\)

Re: Herleitung Geburtstagsproblem/Hashkollisionen

Verfasst: 8. Feb 2013 16:53
von ISTler
\(q \leq e^{-\frac{k(k-1)}{2m}}\)
\(\log(q) \leq -\frac{k(k-1)}{2m}\)
\(-\log(q) \geq \frac{k(k-1)}{2m}\)
\(-2m\log(q) \geq k(k-1)\)
\(2m\log(q^{-1}) \geq k^2-k\)
\(0 \geq k^2-k-2m\log(q^{-1})\)

EDIT: Falsch gedacht, kommt das falsche raus.
EDIT2: Ich hab nochmal länger nachgedacht und auch gegoogelt. Eigentlich müsste die Ungleichung wirklich anders herum sein.
Wenn man statt \(1 + x \leq e^x\) das ungefähre \(1 + x \approx e^x\) nimmt (x bleibt ja zwischen 0 und deutlich über -1) kann man das Ganze richtig biegen.
Ich hab eben nochmal in die Hausübung geschaut. Ich habe sie analog zum Buch gemacht. Die Korrekteurin hat mir dann aber alle Ungleichungen umgedreht.