Introduction
After writing a post about the Monty Hall problem the other day, a friend of mine asked if I’d write one about another famous, counterintuitive probability problem known as the birthday problem. The problem asks a simple(-seeming) question: determine the smallest number of people who must be in a room in order for there to be a 50% chance that two of them share a birthday. (Assume every year has 365 days.)
People typically hear the words “fifty percent” and “birthday” and think something along the lines of: “If there are 365 possible birthdays, then I probably would need about 365/2 people. That’s… **stares up and to the right for a second**… 183 birthdays!” These very people are usually shocked to hear that the solution is far smaller than that, and the rest of this post will show how to calculate it using some probability.
Using probability theory
While the following observation is obvious, it unlocks a new way of solving a whole trove of probability problems: when we consider an event $A$, it either happens or it doesn’t. (We refer to the “it doesn’t” event as $A^C$, read “$A$ complement”.) Thus if the event $A$ happens with a certain probability $p$, then $A$ does not happen with $1 - p$. This allows us to write $P(A)$ in terms of $P(A^C)$ and vice versa. For our purposes, we encode this logic as $P(A) = 1 - P(A^C)$.
To solve the problem at hand, we need to come up with an expression for the probability that two people share a birthday in a room of $k$ people. If we call the aforementioned event $A$, we want an expression for $P(A)$. As per the above, if we can come up with an expression for $P(A^C)$, then we’ve effectively determined our expression for $P(A)$. In our case, the event $A^C$ is the event that in a room of $k$ people, no two share a birthday. The probability of that event is given by:
For the numerator, if we have are looking at a room with 10 people in it, we have 365 birthdays to choose from for the first, 364 for the second, and so on, until you’ve assigned birthdays to all 10 people. The total number of ways is thus $365 \cdot 364 \cdot \dots \cdot 356$.
For a room with k people, we can generalize this to $365 \cdot \dots \cdot (365 - k + 1)$, so that expression is our numerator. To compute the denominator, we are thinking about a more relaxed version of the same assignment problem we solved to compute the numerator. When I say more relaxed, I mean that we don’t have to worry about assigning the same birthdays to people anymore. In our room of 10 people, this means we have 365 birthday choices for the first person, but we also have 365 for the second, third, fourth, fifth and so on. Thus, the total number of ways to assign birthdays to 10 people is $365^{10}$. For a room with $k$ people, this turns into $365^k$.
Now that we have the numerator and denominator, we can write down $P(A^C)$:
With this in hand, we can now use the fact that $P(A) = 1 - P(A^C)$ to express
Now we just start trying values of $k$ until $P(A) \geq 1/2$. This first occurs when $k = 23$.
Intuition
One explanation for why this number is so intuition-defyingly low is that when people first think about this problem, they usually think that $k$ has to do with the number of people in the room, instead of noticing that the key number in this problem is actually the number of pairs of people in the room. While 23 people doesn’t seem like much, 23 people furnishes you with 253 pairs! Each pair has probability 364/365 of not having the same birthday, so the probability that none of the 253 pairs shares a birthday is
This means that the probability that some pair shares a birthday is approximately $1–0.4995 = 0.5005$. To see that the number of pairs is what matters, note that if we increase $k$ to 50, the probability that some pair shares a birthday is roughly 97%. By the time you have 75 at your party, the probability jumps to 99.9%.
Conclusion
As was the case with the Monty Hall problem, the birthday problem serves as an example of the way that a rigorous analysis is a great way to combat our sometimes errant intuition.