Hacker News new | past | comments | ask | show | jobs | submit login
The Birthday Paradox (wikipedia.org)
10 points by the_70x on Sept 25, 2019 | hide | past | favorite | 5 comments

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."

Yes, that is funny.

It feels a bit insane - how do you choose your secret private Bitcoin wallet key? Easy, just pick one randomly! Oh no, but someone else could pick the same key. Sure, but the probably is so vanishingly small, we really really really don't have to worry about it...

It is a bit hard to wrap your head around it, but the maths is solid (assuming, of course, that you have a good source of randomness).

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact