# How many numbers can I generate and be 90% sure that there are no duplicates?

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.

• en.wikipedia.org/wiki/Birthday_problem
– Tim
Jun 6 at 19:13
• @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. Jun 6 at 19:27
• $(365Pn)/(365^n)$ is the probability that no two people have the same birthday Jun 8 at 9:59

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: The approximation by Henry is very close to the exact value, i.e. the black and green dots are basically identical.

• 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. Jun 7 at 2:54
• @Glen_b Thanks, I already forgot about the birthday functions! Jun 7 at 5:37
• 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) Jun 7 at 21:53
• @Henry Thanks for the improvement, I added it to the answer. Do you have a source on this improved approximation? Jun 8 at 10:00
• @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. Jun 8 at 10:19

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!

• 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 Jun 8 at 17:29