Throwback Fact: The Birthday Problem

image: www.flickr.com

In 1939, mathematician Richard von Mises proposed a problem. The answer was so counter-intuitive to many people, including mathematicians across the globe, that it continues to be one of the most discussed math problems ever. It is very difficult for people to understand, not because the mathematics behind it are hard, but just because the answer is so different from what anyone would expect. That problem is stated as follows:

Suppose you are in a large room that random people generally enter. How many people must be in the room before the probability that some share a birthday becomes at least 50 percent?


Now, let's just think about this rationally first. Assuming there are 365 possible birthdays, there is a one in 365 chance that you share your birthday with the second person to enter the room. As long as there are just two of you, there's a 1/365 percent chance that your birthday is shared. On the opposite end of the spectrum, if there are 366 random people in the room, there is a 100 percent chance that at least one birthday is shared (this is due to the Pigeonhole Principle). So for a 50 percent chance of a shared birthday, it'll require abut halfway between 2 and 366 people. Right?

We can assume this pair have matching birthdays.

Wrong. The answer is a mere 23 random people. And if you were looking for a 99 percent chance of any two people in a room sharing a birthday, you need only 57 people. The answer depends on pairs of people. When there are 2 people, only 1 pair is possible. With 3 people, there are 3 pairs possible. With 4 people, there are 6 possible pairs. When you get to 23 people, 253 different pairs are possible, any of which could lead to a matched birthday. For a more detailed (and designed in TeX) explanation, our math intern liked this page.

The answer is so much lower than many would expect because as humans we make assumptions that are irrelevant to the problem. Our minds automatically make the bridge to finding two particular people, or a particular birth date. We overthink automatically, when a match on any date by any two people is sufficient.