Birthday Paradox

Introduction

The birthday paradox is a classic trick that teachers often use to perplex students when they first start learning statistics. Typically, the teacher will slowly pull out a $100 bill and ask the students whether there are two people in the classroom who share the same birthday.

Intuitively, we might think the probability is quite low. However, in reality, as long as there are more than 23 people, the probability that two of them share a birthday exceeds 50%.

One reason for this misconception is that we often conflate the question “Do two people share a birthday?” with “Does anyone share a birthday with you?” but the probabilities of these two scenarios are entirely different.

The probability of "someone sharing your birthday" is $\frac{1}{365}%, whereas the probability of "two people sharing a birthday" increases because the range of possibilities expands. It still seems counterintuitive; logically, we would expect it to grow linearly, right? But actually, once the number exceeds a certain threshold, this probability rises rapidly, which we will discuss below.

Solution

Complement

We can calculate the probability that at least two people share a birthday using the complement method, which means subtracting the probability that all people have different birthdays from 1. So how do we calculate that? Let’s first consider the probability that two people have different birthdays:

The first person has 365 days to choose from, while the second person has 364 days. Next, let’s think about the probability that three people have different birthdays:

Do you see the pattern? If there are n people, the probability is $\frac{365}{365}\times\frac{364}{365}\times\frac{363}{365}\times...\frac{n-1}{365}$.

Thus, the probability we want to calculate is: $P = 1 - \left(\frac{364}{365}\times\frac{363}{365}\times...\times\frac{n-1}{365}\right) \geq 0.5$. Let’s simplify this:

We can apply the property (1+x < e^{x}) to further modify the inequality:

From this, we can observe that because we can approximate using the natural exponential, the growth of the probability will exhibit exponential changes as the number of people increases.

Conclusion

Often, when we learn mathematics, we find ourselves entangled in formulas and peculiar problems without ever considering the true meaning behind these formulas, how they are derived, or more importantly, what problems we are actually trying to solve by learning this mathematics.