Database Reference
In-Depth Information
Hash Collisions and the Birthday Paradox
One of the more famous probability parlor tricks is the so-called
Birthday Paradox. It states that when you get a group of more than 23
people together there will be a 50 percent chance that at least two
people share a birthday. By the time you have 60 people, there is a
better than 99 percent chance that at least two of them will share a
birthday.
When you think of birthdays as a simple hash function that maps each
person into a number between 1 and 365, then sharing a birthday is
basically a hash collision. Knowing the mathematics behind the
paradox is useful for understanding many of the calculations in the next
sections. Also, it's a nifty trick to use at parties.
To start, assume that birthdays are evenly distributed through the year,
just like hash functions uniformly distribute their values. In reality,
birthdays are not quite evenly distributed throughout the year, and leap
years are a problem, but that is a discussion for a different book.
The easiest way to compute the probability that at least two people
share a birthday is to compute the probability that nobody in the room
shares a birthday. In this case the first person can choose whatever day
she wants so she can have any possible birthday A. The second person
cannot choose the birthday the first person chose, so he chooses a
birthday B from one of the 364 remaining birthdays. The third person
chooses birthday C, and so on up to n people. Writing down the
probability is:
rewritten as,
Where ! represents the factorial function, the product of all integer
values from 1 to n. So, 5! Is 5×4×3×2×1.
