Preface

The birthday paradox is a trick that teachers often use to confuse students when they first learn statistics. Usually, the teacher would slowly take out 100 yuan from their wallet and ask the students if there are two people in the classroom who share the same birthday.

Intuitively, we might think that the probability is very low. However, the fact is that once we have more than 23 people, the probability of two people sharing the same birthday is over 50%.

Part of the reason is that we associate the question "two people sharing the same birthday" with "someone sharing the same birthday as you," but the probabilities of the two are completely different.

The probability of "someone sharing the same birthday as you" is $\frac{1}{365}%, but the probability of "two people sharing the same birthday" increases because the range becomes wider. However, it still goes against intuition. In theory, it should show linear growth, right? But in fact, once we exceed a certain value, this probability increases rapidly, which we will discuss below.

Solution

Complement

We can calculate the probability of at least two people sharing the same birthday by using the complement, which is 1 minus the probability that everyone's birthday is different. So how do we calculate it? Let's first think about the probability of two people having different birthdays:

The first person has 365 days to choose from, while the second person has 364 days. Now let's think about the probability of three people having 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}$

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$ Let's simplify it:

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

From here, we can observe that because we can approximate it with the natural exponential function, the growth of the probability also exhibits exponential change as the number of people increases.

Conclusion

Many times, when we learn mathematics, we are often bewildered by formulas and peculiar questions, but we never really think about the true meaning behind the formulas, how they are proven, or more importantly, what problems we are actually trying to solve by learning these mathematics.