0
$\begingroup$

This question already has an answer here:

If I have a device that displays a random number from 1 to 10 billion and I use that device X times, what is the probability that not all of the numbers displayed are unique?

$\endgroup$

marked as duplicate by Michael Chernick, whuber probability Feb 6 at 21:30

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.

  • 4
    $\begingroup$ en.wikipedia.org/wiki/Birthday_problem $\endgroup$ – Alex R. Feb 6 at 19:34
  • $\begingroup$ It seems like it is explained here: en.wikipedia.org/wiki/… But I don't really understand those formulas. $\endgroup$ – Andrew Downes Feb 8 at 10:25
  • $\begingroup$ Thanks for sharing that. The article says "By the pigeonhole principle, the probability reaches 100% when the number of people reaches 367 (since there are only 366 possible birthdays, including February 29). However, 99.9% probability is reached with just 70 people, and 50% probability with 23 people." Can I assume that those proportions also apply if we increase from 366 options to 10 million? I.e. when we have used 23/366 * 10,000,000 = 630,000,000 ish random numbers, the probability of collision is 50%? $\endgroup$ – Andrew Downes Feb 8 at 11:23
  • 1
    $\begingroup$ If you want to find out of $10^9$ how many you need to pick to make the probability of collision 50%, you can use the formula (given on the Wikipedia page) $n(p; d)\approx\sqrt{2d\cdot\ln\left(\frac{1}{1 - p}\right)}$. Since $n(0.5; 10^9) \approx 37233$, there will be a 50% probability of collision when you have around 37233 items. $\endgroup$ – leekaiinthesky Feb 8 at 20:17

Browse other questions tagged or ask your own question.