The birthday paradox is very famous in probability. If you take 23 people, there's about a 50/50 chance that two of them share a birthday. With 50 people, it's a 97% chance.
We could make many other fun examples to illustrate the same counterintuitive phenomenon (thread).
We could make many other fun examples to illustrate the same counterintuitive phenomenon (thread).
Choose a random card from a deck of 52 cards. Put it back, shuffle well, and choose another. Do this for only 9 draws, and more likely than not, you've pulled the same card twice.
Do it 16 times, and your chances are over 90%. Try it!
Do it 16 times, and your chances are over 90%. Try it!
Next time you're in an event with more than 118 people, think to yourself that there's a >50% chance that two people there have phone numbers with the same last four digits (assuming those are uniformly distributed).
With more than 250 people, its >95%.
Ditto for ATM pin codes.
With more than 250 people, its >95%.
Ditto for ATM pin codes.
The number of possible poker hands is 2,598,960. One hand for every person in Chicago, or 10 for each mile between the earth and the moon.
How many hands would you think you'd have to draw before you've likely had the same *exact* hand twice?
It's about 100.
How many hands would you think you'd have to draw before you've likely had the same *exact* hand twice?
It's about 100.
Haha just kidding, that'd be insane.
It's actually around 1,900 hands that it becomes more likely than not to have held the same hand twice. That's just 19 evenings with 100 hands each. Many (most?) of you reading this have held the same exact poker hand twice!
It's actually around 1,900 hands that it becomes more likely than not to have held the same hand twice. That's just 19 evenings with 100 hands each. Many (most?) of you reading this have held the same exact poker hand twice!
You can think of the birthday paradox by asking the probability of drawing 23 people successively so that each one has a birthday not yet seen.
This gives the probability of no collision, so the probability of a collision is 1 minus this.
This gives the probability of no collision, so the probability of a collision is 1 minus this.
The general formula for the probability of a collision when making k choices from a collection of N possibilities looks like this.
By using some approximations for the factorials, it so happens that the inflection point where things shift from collisions being very unlikely to instead being likely is around sqrt(N). More specifically, it happens a little above sqrt(N).
For example, sqrt(365) = 19.105..., and it's at 23 people that you're more likely to have a birthday collision than not.
In the phone numbers example, sqrt(10,000) = 100, and the 50% point happens with 118 people.
In the card example, sqrt(52) = 7.2, and it took 9 draws.
In the phone numbers example, sqrt(10,000) = 100, and the 50% point happens with 118 people.
In the card example, sqrt(52) = 7.2, and it took 9 draws.
This is actually very relevant to cryptography, and goes under the hilarious sounding name of a "Birthday attack"
en.wikipedia.org/wiki/Birthday_…
en.wikipedia.org/wiki/Birthday_…
Specifically, if you have a hash function with N possible outputs (say 2^128), and your system's security depends on collisions never happening, you might initially think an attacker needs around 2^128 brute force attempts, but really it's much *much* smaller: 2^64.
Also, as a loosely related side note, I remain both amused and concerned with how many people didn't realize the tweet below was a joke.
