How many keys before an eleven-bit token repeats?

Question

A service issues an 11-bit token to each request, an independent uniform draw from 2^{11} = 2048 possible values. What is the smallest number of tokens issued before a repeated value becomes more likely than not?

Accepted Answer

Find the smallest n with P(	ext{all distinct}) \le 	frac12. Each of the \binom{n}{2} pairs collides with probability 1/2048, and P(	ext{all distinct}) \approx e^{-\binom{n}{2}/2048}. Setting this to 	frac12: \frac{\binom{n}{2}}{2048} \approx \ln 2 = 0.693 \implies \binom{n}{2} \approx 1420 \implies n \approx 54. Checking the exact product: at n = 53 the repeat probability is about 0.49, and at n = 54 it is about 0.51. So n = 54. The shortcut n \approx 1.18\sqrt{d} gives 1.18\sqrt{2048} \approx 53.3, rounding up to 54. This is exactly the "birthday attack" idea in cryptography: an 11-bit t…

How many keys before an eleven-bit token repeats?

Your answer

More Probability questions