The Birthday Paradox

Rule of thumb (useful for cryptography, among other things):

If you draw randomly (with replacement) from N numbers, you'll need to draw approximately sqrt(N) times until the probability of a collision (drawing the same number again) rises to 1/2.

For example, if you generate random keys with 128 bits, then after generating 2^64 keys you have a good (50%) chance that you've reused a key.

See https://en.wikipedia.org/wiki/Birthday_attack

As FabHK[0] says[1], the rule of thumb is that you are 50% likely to get a collision with about sqrt(N) selections from N objects.

We are, of course, more interested in much smaller probabilities of collision, and that's why I wrote about this[2] some time ago, giving the derivation, and the actual formula for those who just want the answer.

It's been submitted and discussed before[3][4], with some interesting comments.

[0] https://news.ycombinator.com/user?id=FabHK

[1] https://news.ycombinator.com/item?id=21069837

[2] https://www.solipsys.co.uk/new/TheBirthdayParadox.html?si25h...

[3] https://news.ycombinator.com/item?id=19296265

[4] https://news.ycombinator.com/item?id=4753014

I just recently published a blog post on this topic: https://www.mcherm.com/unique-ids.html

Sadly, I am still getting pushback from others at my company who are either not convinced by the math or for whom any such analysis doesn't matter. "Yes, but there is still a chance of getting a duplicate, so I don't think this can be safe."

Related: https://en.wikipedia.org/wiki/Birthday_attack

Also shameless plug: https://blog.rinatussenov.com/collision-probability-and-birt...