approximating the birthday problem
Given possible outcomes, how many random samples must be taken so that with a probability of at least there are two equal samples?
Answer: Approximately samples must be taken.
So in the typical birthday problem setting the – the number of days in the typical year, and the result is that 23 people in a group gives at least a 50% chance of two people with a common birthday. This result can be obtained by a concise computation of the probilities for various sizes of the group until the proper value of 23 is found, but this approach does not lend itself to finding the value of 23 efficiently.
The result however has an easy to compute approximation of , so in the case of , the result is approximated by . We now validate the estimate.
Recall the probability of selecting a duplicate from possible outcomes within choices is
we can roughly approximate the formal product above by:
Now we are after a formula in which given and the desired probability of we can estimate . So we solve for in the equation:
A less precise but easier to compute approximation comes from simplifying our original estimate further:
Then set and once again solve for to find:
We also see that if we wish to have an outcome with probability of no matches then we can estimate the sample size by:
So the number of samples required to find a match with probability is approximately
- 1 Wikipedia, Birthday paradox, http://en.wikipedia.org/w/index.php?title=Birthday_paradox&oldid=69569553. Accessed 14 August, 2006.
|Title||approximating the birthday problem|
|Date of creation||2013-03-22 16:09:56|
|Last modified on||2013-03-22 16:09:56|
|Last modified by||Algeboy (12884)|