How many tokens before a duplicate is likely?

Question

A system hands out session tokens, each an independent uniform draw from 1000 possible codes. What is the smallest number of tokens issued before a duplicate token becomes more likely than not?

Accepted Answer

We want the smallest n with P(	ext{some duplicate}) \ge 	frac12, equivalently P(	ext{all distinct}) \le 	frac12. The chance all n tokens are distinct is the running product P(	ext{all distinct}) = \frac{1000}{1000}\cdot\frac{999}{1000}\cdots\frac{1000-(n-1)}{1000}. A fast estimate uses the fact that each of the \binom{n}{2} pairs collides with probability 1/1000, and P(	ext{all distinct}) \approx e^{-\binom{n}{2}/1000}. Setting this to 	frac12: \frac{\binom{n}{2}}{1000} \approx \ln 2 = 0.693 \implies \binom{n}{2} \approx 693 \implies n \approx 38. Checking the exact product confirms it…

How many tokens before a duplicate is likely?

Your answer

Discussion

Learn the concepts

Related questions