Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Birthday-coverage problem

An example of what I wish to do is the following: http://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?

share|improve this question

marked as duplicate by Qiaochu Yuan Sep 14 '11 at 15:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Are you assuming that birthdates are uniformly-distributed? There is data that leads to reasonably questioning this belief/assumption. –  gary Sep 14 '11 at 4:29
1  
See this question, where exact calculations, very tight approximations, hard bounds, and the expected value can all be found in the various answers. –  cardinal Sep 14 '11 at 10:15
add comment

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
The ln function is great, I never thought it could be this easy. Thank you for your steps. –  Donaldt Fourier Sep 16 '11 at 1:16
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.