2
$\begingroup$

Possible Duplicate:
Birthday-coverage problem

An example of what I wish to do is the following: https://stackoverflow.com/questions/4681913/substr-md5-collision/4785456#4785456

How would I calculate how many people would be required, as in the link above, to reach 50% or 0.001% or n% probability of collision exactly?

I am able to calculate the likelyhood of a collision in say a hash, with

$1-e^\frac{-n^2}{(2*10^6)}$

10^6 being six numerical digits from zero to nine. However, I would have to guess a lot of times before I got the exact number of people it would take to reach exactly 50%, which may be a fraction (i.e. 20.2 people)

How would I be able to find this?

  • 1
    See [this question](http://math.stackexchange.com/questions/26772/birthday-coverage-problem), where exact calculations, very tight approximations, hard bounds, and the expected value can all be found in the various answers.2011-09-14

1 Answers 1

4

I'm somewhat confused by the question because it contains the word "exact" four times but you suggest to calculate the probability of a collision using a relatively simple approximation. For this answer, I'll assume that you're aware that there are better approximations for this probability, and of the various answers you get by searching for "birthday" on this site, and that your question is only about calculating $n$ given $1-\exp(-n^2/(2k))$. This you can do by solving for $n$ as follows:

$ p=1-\mathrm e^{-n^2/2k}\;, $ $ \mathrm e^{-n^2/2k}=1-p\;, $ $ -\frac{n^2}{2k}=\log(1-p)\;, $ $ n^2=-2k\log(1-p)\;, $ $ n=\sqrt{2k\log(1-p)}\;, $

where $\log$ is the natural logarithm, i. e. the logarithm to base $\mathrm e$.

  • 0
    It seems to me that the last equation omits the - before 2k.2018-11-20