Revisiting the Birthday Paradox

Introduction

The Birthday Paradox is a classic trick statistics professors love to use to baffle students when starting out in a course. Typically, the professor slowly pulls out a $100 bill from their wallet and asks the class: “Are there any two people in this room who share a birthday?”

Intuitively, we might assume the probability is quite low. In reality, however, as long as there are 23 or more people, the probability that at least two people share a birthday is over 50%.

Part of the reason for this misconception is that we tend to conflate the question “Do any two people share a birthday?” with “Does someone share a birthday with you?” But the probabilities of these two scenarios are completely different.

The probability of “someone sharing a birthday with you” is $\frac{1}{365}%, but with “any two people sharing a birthday”, because the scope expands, the probability naturally increases. Still, it feels somewhat counterintuitive—logically, shouldn’t it grow linearly? In fact, once past a certain threshold, this probability climbs rapidly, as we will discuss below.

The Solution

Complementary Probability

We can calculate the probability of at least two people sharing a birthday using the complementary event—that is, subtracting the probability that everyone has a distinct birthday from 1. So how do we calculate this? Let’s first consider the probability of two people having different birthdays:

(The first person has 365 days to choose from, and the second person has 364 days). Next, let’s consider the probability of three people having distinct birthdays:

Notice 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}$

So the probability we want to calculate is: $P=1-(\frac{364}{365}\times\frac{363}{365}\times...\frac{n-1}{365}) \geq 0.5$ Simplifying this:

We can make use of the property $1+x\lt e^{x}$ to further transform the inequality:

From this, we can see that because it can be approximated using the natural exponential, the probability’s growth behaves exponentially as the number of people increases.

Conclusion

All too often when learning mathematics, we get overwhelmed by formulas and bizarre problem sets without ever pondering the real meaning behind these formulas, how they were proven, or more importantly, what problems we are actually trying to solve by learning this math.