The Problem

Imagine walking into a room full of strangers. At first, everyone seems completely unrelated, with different names, different lives, and different birthdays. As the room gets more crowded, we of course know that sharing similarities with the strangers in the room becomes more likely.

But just how likely is it that, for example, two people in the room share a birthday?

The Birthday Paradox asks, more specifically: How many people must be in the room so that it is more likely than not that two people share a birthday?

Intuitively, we might imagine it must be well over 100 since there are 365 possible birthdays that each stranger can have. Probability, however, has a habit of ignoring our intuition.

Building the Math

Suppose there are only two people in the room: you, and one stranger. You have your own birthday, so there is a 1/365 ≈ 0.27% chance that the stranger next to you shares your birthday. If we add a third person to the room, we must consider the probability that either of the two strangers share your birthday, or the two strangers share a birthday with each other. This overlap makes our calculations more difficult, and it will only get worse as we add more people.

Instead, there's a cleaner way to find the solution. Let's find the probability P(n) that no two people share a birthday, then subtract it from 1 to get the probability that two people do share a birthday. Once P(n) < 0.5, then 1 - P(n) > 0.5, meaning at this value of n, there is a greater than 50% chance that two people in the room share a birthday.

For the case of only two people, there is a 364/365 chance that the second person has a different birthday than the first person. If we introduce a third person, there are 363 unclaimed birthdays left in the year, so a 363/365 chance that the third person's birthday falls on one of these days. Repeating this process for n people in the room, we get:

If we keep increasing n, we see that the probability P(n) that two people don't share a birthday decreases, meaning the probability 1 - P(n) that they do share a birthday increases.

Below are some values of 1 - P(n) I found using Maple Learn:

Based on these calculations, we see that when 23 people are in the room, it is more likely than not that at least two people in the room share a birthday.

Extending the Problem

Our question was very specific: we wanted to know what n needed to be in order for the probability of two people sharing a birthday to be > 50%. We found this number to be 23. But, we could extend this question to, say, the probability being 99.9%. This happens when there are 70 people in the room. Consider the animation below to see this visually, where the x-axis represents the number of people n, and the y-axis represents the probability that two people share a birthday, 1 - P(n):

Limitations

How many people must be in the room to guarantee that two of them share a birthday? By the shape of the graph above, it may be tempting to think that it is impossible to guarantee this, since the probability seems to asymptotically approach 1. However, we must think through this logically.

If 365 people were in the room, it is still possible that their birthdays would all fall on a different day (although it's extremely unlikely). But if we have more people than we have available birthdays, we can say at least two people will share a birthday with 100% certainty. That is, P(n) = 0 when n > 365, so our formula for P(n) above is limited to values of n that are 365 or less. This is a basic principle in mathematics called the "pigeonhole principle", which uses the analogy that if we have more pigeons than we have holes to put them in, then at least one of the holes must have at least two pigeons.

These ideas can be conceptually confusing, but once you go through the mathematical arguments a few times, mentioning the Birthday Paradox in a conversation is a great way to show off your random math knowledge and confuse your peers!

Attached is an interactive Maple worksheet from Maple's Math Apps gallery if you'd like to investigate the Birthday Paradox further: The_Birthday_Paradox.mw. If you're still interested in more info/applications, see this Maple Primes post by John May.