4 ms·
The Birthday Paradox
- mcherm 7y agoI just recently published a blog post on this topic: https://www.mcherm.com/unique-ids.html 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."
- FabHK 7y agoYes, 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).
- FabHK 7y agoRule 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 https://en.wikipedia.org/wiki/Birthday_attack
- ColinWright 7y agoAs 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 https://news.ycombinator.com/user?id=FabHK [1] https://news.ycombinator.com/item?id=21069837 https://news.ycombinator.com/item?id=21069837 [2] https://www.solipsys.co.uk/new/TheBirthdayParadox.html?si25hn https://www.solipsys.co.uk/new/TheBirthdayParadox.html?si25h... [3] https://news.ycombinator.com/item?id=19296265 https://news.ycombinator.com/item?id=19296265 [4] https://news.ycombinator.com/item?id=4753014 https://news.ycombinator.com/item?id=4753014
- rinchik 7y agoRelated: https://en.wikipedia.org/wiki/Birthday_attack https://en.wikipedia.org/wiki/Birthday_attack Also shameless plug: https://blog.rinatussenov.com/collision-probability-and-birthday-paradox-ef98b84fe009 https://blog.rinatussenov.com/collision-probability-and-birt...