21
$\begingroup$

Suppose I am generating random 4-digit numbers. Obviously there are 10,000 possible numbers, but the chances are I will get a duplicate long before I generate that many.

Can anyone explain how I would work out how many numbers I would be able to generate and still be (say) 90% sure that there weren't any duplicates?

To be clear, I am treating these numbers as strings, so all will have four digits, even if there are leading zeroes. Also, I'm using a random number generator, so am assuming that any 4-digit number is as likely to be generated as any other.

Improve this question
$\endgroup$
3
  • 11
    $\begingroup$ en.wikipedia.org/wiki/Birthday_problem $\endgroup$
    – Tim ♦
    Jun 6 at 19:13
  • $\begingroup$ @Tim Thanks for the link. If I understand correctly, using the last method shown, the probability of at least 2 people out of n sharing a birthday is (365Pn)/(365^n), then applying it to my question, the probability of any two numbers out of 10,000 generated being the same would be (10000P4)/(10000^4), which is around 0.04. Is that correct? Thanks again. $\endgroup$
    – Avrohom Yisroel
    Jun 6 at 19:27
  • $\begingroup$ $(365Pn)/(365^n)$ is the probability that no two people have the same birthday $\endgroup$
    – Taladris
    Jun 8 at 9:59

2 Answers 2

Reset to default
32
$\begingroup$

The approximation given in the Wikipedia article (also mentioned in the paper by Diaconis & Mosteller (1989)) works well here. Suppose $N$ 4-digit numbers are drawn with replacement from a pool of $c$ possible numbers, $N\leq c$. According to Diaconis & Mosteller (1989), if $c$ is large and $N$ is small compared to $c^{2/3}$, the following approximation is useful. An approximation for the probability of no duplicates is $$ \exp(-N^2/2c) $$ You want this probability to be $\geq90\%$. In your case, $c = 10^4$. Solving the equation (there are two solutions but only one is positive) for $N$ so that $\exp(-N^2/2c)\geq0.9$ gives $N\leq \sqrt{-\log(0.9)\times2\times10^4}= 45.9044$. So you can draw around $46$ at most and more than that will result in a greater than $10\%$ probability of duplicates. In general, replace $0.9$ with the desired probability of no duplicates. This formula is also given in the Wikipedia article.

Thanks to @Henry, a better approximation to the probability of no duplicates is $$ \exp(-N(N-1)/2c) $$ resulting in $N\leq\sqrt{1/4 - 2c\log{(p)}} + 1/2$. Using your situation, we get $N\approx 46.4071$ with a probability of no duplicates of $0.9017$ which is extremely close to the true probability of $0.9015$.

R provides the functions pbirthday and qbirthday that calculate the probabilities of no duplicates exactly.

Here is a plot comparing the two approximations with the exact probabilities in the relevant range:

Comparison

The approximation by Henry is very close to the exact value, i.e. the black and green dots are basically identical.

Improve this answer
$\endgroup$
6
  • 11
    $\begingroup$ As a quick check, R comes with p and q functions for this. qbirthday(.1,10000) gives 47 while pbirthday(47,10000) gives 0.1026129 and pbirthday(46,10000) gives 0.09846583 Yes, it looks like you're right, the approximation seems to work quite well. $\endgroup$
    – Glen_b
    Jun 7 at 2:54
  • $\begingroup$ @Glen_b Thanks, I already forgot about the birthday functions! $\endgroup$
    – COOLSerdash
    Jun 7 at 5:37
  • 3
    $\begingroup$ You can get slightly closer than the approximations $p \approx \exp\left(-\frac{N^2}{2c}\right)$ and $N \approx \sqrt{-2c\log(p)}$ with $p \approx \exp\left(-\frac{N(N-1)}{2c}\right)$ and $N \approx \sqrt{\frac14-2c\log(p)}+\frac12$. So with $c=10^4$ and $N=46$ you get about $0.9017$ instead of $0.8996$ and closer to the true $0.9015$; with $p=0.9$ you get less than or equal to about $46.407$ instead of $45.904$ (using the gamma function would suggest about $46.372$ is the best you can do) $\endgroup$
    – Henry
    Jun 7 at 21:53
  • $\begingroup$ @Henry Thanks for the improvement, I added it to the answer. Do you have a source on this improved approximation? $\endgroup$
    – COOLSerdash
    Jun 8 at 10:00
  • 2
    $\begingroup$ @COOLSerdash The Wikipedia article you link to derives $\bar p(n) \approx e^{-\frac{n(n-1)}{2 \times 365}}$ before saying $\bar p(n) \approx e^{-\frac{n^2}{2 \times 365}}$ is an "even coarser approximation". My approximate expression for $N$ just solves the quadratic. $\endgroup$
    – Henry
    Jun 8 at 10:19
14
$\begingroup$

The other answer uses an approximation. Here is an answer with an exact formula.

The probability that there are no duplicates when drawing $k$ numbers among $N=10000$ is : $$P_{N,k} = \frac{\text{number of draws without duplicates}}{\text{total number of draws}} = \frac{\frac{N!}{(N-k)!}}{N^k} = \frac{N!}{{N^k}(N-k)!}$$

This is a strictly decreasing function of $k$. You want to know the largest value of $k$ such that this probability is still higher than $90%$.

We can find it with a quick binary search computer program: $$P_{10000, 46} = 90.15\%$$ $$P_{10000, 47} = 89.74\%$$

So the final answer is: you can draw 46 numbers.

This is matched very closely by the value of 45.9 found by the approximation formula!

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for your very clear answer. It was hard to choose which one to mark, so please don't be offended that I chose COOLSerdash's $\endgroup$
    – Avrohom Yisroel
    Jun 8 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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