The Matching Birthday Problem

Published:  04/06/2014

Several years ago, I encountered a probability problem that was quite interesting. After first reading the problem, it seemed very difficult. The problem went something like this:

"Ignoring leap years, find the probability that a room containing n people has at least two people with the same birthday (same month and day, not year)."

This problem is a challenge for two reasons. First, the room size is not given as a constant, which means the solution must be expressed as a formula involving n. Second, even if we assumed a fixed room size, there are a lot of possible ways to have one or more matching birthdays. For example, imagine the room has just four people in it. We will call them A, B, C, and D. Then there is a match when A and B have a birthday in common, or A and C, or A and D, ... Let's try to list all of the cases where there could be a match.

There are eleven unique scenarios where we would have at least one matching set of birthdays. It's a good thing that we didn't imagine a room with twenty people in it! After forming the list above, we would calculate the probability for each of those scenarios.

Once each individual probability is calculated, we can obtain the probability of a room of four people having at least two people in it with the same birthday by adding together the probabilities for each of the eleven cases. Now, imagine having to do this for all of the rooms of size n, where n ranges from 2 to 365*. That would be a daunting task, but there is an easy way out of taking this approach.   

The Probability of At Least One

There is a very handy formula in probability which is based on the idea of complements. The event that at least one of something occurs is complementary with the idea that none of that something occurs. For example, isn't it true that you either received no speeding tickets last year, or you received at least one speeding ticket last year? Because that is true, the probability that you received no tickets plus the probability that you received at least one ticket must be 100%.

P(no tickets) + P(at least one tickets) = 1 (or 100%)

Using some simple algebra, we can subtract P(no tickets) from both sides to get:

P(at least one ticket) = 1 - P(no tickets)

We can generalize this relationship by saying the "P(at least one) = 1 - P(none)." Now, all we need to do is to approach the birthday problem using this same logic.

P(at least one pair of matching birthdays) = 1 - P(no pairs of matching birthdays)

We want the answer for the quantity on the left-hand side (for a room with n people), so the formula is telling us that all we need to do is to find the P(no pairs of matching birthdays). How do we find the probability that no one in the room has the same birthday as anyone else? Luckily, that can only happen one way. Imagine you are the first person in the room and that you are born on January 1st (Actually, the day could be any day; it doesn't have to be Jan. 1). What is the probability that there is no match in the room at this point? Since only you are in the room, the probability of no match is 100% (let's write this as 365/365). Let's continue to fill the room in our minds with people in a way that will guarantee there are no matching birthdays. When the second person comes into the room, that person can have any birthday as long as it isn't January 1st because that birthday is taken (364 other days are available though), and remember, we do not want to have a match. What is the probability that after two people enter the room there is no match? The probability is now 365/365*364/365. The third person, to enter the room, can have any birthday other than the two birthdays already in the room, and so on and so forth, until the room is filled. Here are the corresponding probabilities so far:

P(no one in the room of size n has the same birthday) = 365/365*364/365*363/365*...

What should the fraction be for the nth person to enter the room? Well, notice that by the third fraction, which represents the third person, we have subtracted 2 from 365. That is one less than the person's position in the room. Thus, the general term will be [365 - (n - 1)]/365 = (365 - n + 1)/365.  Putting it all together, we have:

P(no one in the room of size n has the same birthday) = 365/365*364/365*...*(365 - n + 1)/365.   

Finally, the probability we are solving for will be:

P(at least one pair of matching birthdays) = 1 - P(no one in the room of size n has the same birthday)

P(at least one pair of matching birthdays)= 1 - [365/365*364/365*...*(365 - n + 1)/365].

Performing the Calculation

Now, what if n is 25? This formula will still require a lot of calculations, so I wrote a program in the graphing calculator to do the calculations. See the next blog on how to program this into the TI-83 graphing calculator, and I work out some examples with the calculator there as well.

* It takes at least 2 people to have a match, and once the room reaches 366 people, there has to be a matching birthday because there are only 365 available days to be born on in the year.