The Birthday Paradox

Published on 2025-02-27

The Paradox

In a room with 23 people, there's a 50% chance that at least two of them have the same birthday.

Sounds like nonesense, but it's true! In order to show why this is the case, we could try to list all the possible ways in which at least two people could share a birthday, calculate the probabilities for each, and add them up. However, there is a much simpler way to think about this.

An event either takes place or doesn't. That means that the probability that it does plus the probability that it doesn't equals to 1. This seems like a trivial observation, but it's critical for solving many problems like this one: calculating the probability of one of those events is enough to obtain the probability for the other one.

Instead of thinking about all the possible ways in which at least two people could share a birthday, let's consider the event in which none of them do.

The (Simplified) Problem

What is the probability that, in a set of $n$ randomly chosen people, none of them share a birthday?

Let's make a few assumptions first in order to simplify the problem:

There are no leap years
Birthdays are equally distributed among the set of all possible dates

With these assumptions in place, let's proceed to solve it.

The Solution

Let's represent each birthday with $b_{1}, b_{2}, \dots, b_{n}$ . For a given value of $b_{1}$ , and in order to prevent shared birthdays, $b_{2}$ can have one of $365 - 1 = 364$ possible values, which will happen with a probability of $\frac{364}{365}$ . Assuming this happens, for given values of $b_{1}$ and $b_{2}$ , and to keep preventing shared birthdays, $b_{3}$ can have one of $365 - 2 = 363$ possible values, which will happen with a probability of $\frac{363}{365}$ . In general, given values of $b_{1}, b_{2}, \dots, b_{n - 1}$ , there's a probability of $\frac{365 - n + 1}{365}$ that $b_{n}$ won't share a birthday. So in total, given $n$ people, the probability $P_{n}$ that nobody shares a birthday with anyone is:

\begin{matrix} P_{n} & = \frac{365 - 1}{365} \cdot \frac{365 - 2}{365} \dots \frac{365 - n + 1}{365} \\ = \frac{365!}{365^{n} \cdot (365 - n)!} \end{matrix}

Thus, the probability that at least two people share a birthday is:

1 - P_{n} = 1 - \frac{365!}{365^{n} \cdot (365 - n)!}

In particular, $P_{23} \approx 0.493$ , and $1 - P_{23} \approx 0.507$ , which shows that this so-called paradox is indeed true.