The Birthday Paradox, math that surprises you lesson

Twenty-three people are in a room. What is the chance that at least two of them share a birthday? With 365 days to choose from, a match sounds unlikely, yet in the standard model the probability is a little more than one half. This page states that model, counts the 253 pairs of people who could match, and finds the exact probability by computing the chance that all the birthdays differ and subtracting it from one.

Key terms

Birthday problem

Definition The birthday problem asks for the probability that at least two of $n$ people share a birthday, meaning the same month and day. The matching people are not named in advance, so a match between any two of them counts. The standard model ignores February 29 and makes two assumptions. Each person’s birthday is one of the remaining $365$ days, each with probability $1/365$ , and the birthdays of different people are independent, so knowing some of them does not change the chances for the others. In this model, for every $n \ge 1$ ,

\begin{aligned} &P(\text{shared birthday}) \\[0.4em] &\quad = 1 - \prod_{k=0}^{n-1} \frac{365 - k}{365}, \end{aligned}

where the product multiplies the fractions $365/365$ , $364/365$ and so on, one for each person. For $n \ge 366$ the product contains the factor $0$ , so a shared birthday is certain, as it must be with more people than days. For $n = 23$ the probability is about $0.507$ , and $23$ is the smallest group for which it is more than one half. The word paradox in its popular name refers to the surprise, not to a contradiction. Real groups differ from the model, since births are not spread exactly evenly over the year, some people are born on February 29, and twins share a birthday. For people whose birthdays are independent and follow one common uneven pattern over the $365$ days, the unevenness cannot make a match less likely than in the model. The lesson Birthday and Collision Problems in the probability course treats the same question for any number of equally likely categories.

In plain words The question is whether any two people match, not whether someone matches you. A group of $23$ contains $253$ pairs, and each pair is one more chance for a match.

Example For $23$ people the probability that all birthdays differ is about $0.4927$ , so a shared birthday has probability about $1 - 0.4927 = 0.5073$ , or $50.7$ percent. A match is only slightly more likely than no match, so a group of $23$ without a shared birthday is an ordinary outcome, not evidence against the calculation. The probability grows steadily with the group, about $47.6$ percent for $22$ people, $70.6$ percent for $30$ and $97.0$ percent for $50$ . The narrower question of whether at least one of the other $22$ people shares one particular person’s birthday has probability

1 - \left(\frac{364}{365}\right)^{22} \approx 0.0586,

about $6$ percent, because it looks at only $22$ of the $253$ pairs.

Number of pairs

Definition A group of $n$ people contains

\binom{n}{2} = \frac{n(n - 1)}{2}

different pairs, for every whole number $n \ge 0$ . The symbol $\binom{n}{2}$ is read ” $n$ choose $2$ ”. To see the formula, count ordered pairs first. There are $n$ choices for the first person and $n - 1$ for the second, and each pair has been counted twice, once in each order. Adding people one at a time gives the same count, since the $k$ th person to arrive forms $k - 1$ new pairs, one with each person already present, and $0 + 1 + \cdots + (n - 1) = n(n - 1)/2$ .

In plain words The number of pairs grows much faster than the number of people. Doubling a group of two or more people more than quadruples its number of pairs.

Example A group of $23$ people has

\frac{23 \cdot 22}{2} = 253

pairs. One particular person belongs to only $22$ of them, and the other $231$ pairs do not involve that person. The many pairs explain why a match is likely, but they do not give its probability directly. Each pair matches with probability $1/365$ , and adding these gives $253/365 \approx 0.693$ , which is too large. In one room several pairs can match at once. For example, three people born on the same day form three matching pairs, and the sum counts such a room three times, once for each matching pair, where the probability of at least one match counts it once.

Complement rule

Definition The complement of an event $A$ is the event that $A$ does not happen, written $A^{c}$ . Every outcome lies in exactly one of $A$ and $A^{c}$ , so

P(A) = 1 - P(A^{c}).

The complement of the event that at least two of $n$ people share a birthday is the event that all $n$ birthdays are different.

In plain words When an event can happen in many overlapping ways, it is often easier to find the chance that it does not happen at all and subtract that from one.

Example A shared birthday can mean one matching pair, several matching pairs, or three or more people on one day, and counting all these directly is hard. The complement, that all $23$ birthdays are different, is a single condition. Its probability is about $0.492703$ , so

\begin{aligned} &P(\text{shared birthday}) \\[0.4em] &\quad \approx 1 - 0.492703 \\[0.4em] &\quad = 0.507297. \end{aligned}

Multiplication rule

Definition For events $A$ and $B$ with $P(A) > 0$ , the multiplication rule states that

\begin{aligned} &P(A \cap B) \\[0.4em] &\quad = P(A)\,P(B \mid A), \end{aligned}

where $A \cap B$ is the event that both happen and $P(B \mid A) = P(A \cap B)/P(A)$ is the conditional probability of $B$ given $A$ , the probability of $B$ once $A$ is known to have happened. For events $A_1, \dots, A_n$ with $P(A_1 \cap \cdots \cap A_{n-1}) > 0$ , using the rule repeatedly gives

\begin{aligned} &P(A_1 \cap \cdots \cap A_n) \\[0.4em] &\quad = P(A_1)\,P(A_2 \mid A_1) \cdots \\[0.4em] &\quad P(A_n \mid A_1 \cap \cdots \cap A_{n-1}). \end{aligned}

When the events are independent, every conditional probability equals the plain probability $P(A_k)$ , and the right side is simply $P(A_1)\,P(A_2) \cdots P(A_n)$ .

In plain words To find the chance that a whole chain of steps succeeds, multiply the chance that the first step succeeds by the chance that the second succeeds given that the first did, and so on. Each factor is worked out as if all the earlier steps have already succeeded.

Example Let $A_k$ be the event that person $k$ has a birthday different from everyone before. Given that the first $k - 1$ birthdays are all different, they occupy $k - 1$ days, and because birthdays are independent and equally likely, person $k$ avoids those days with probability $(365 - k + 1)/365$ . The factors therefore run from $365/365$ for the first person, who cannot match anyone, down to $343/365$ for person $23$ , who must avoid $22$ occupied days, and

\begin{aligned} &P(\text{all 23 different}) \\[0.4em] &\quad = \frac{365}{365} \cdot \frac{364}{365} \cdots \frac{343}{365} \\[0.4em] &\quad \approx 0.4927. \end{aligned}

The condition in each factor matters. The third person has $363$ safe days only when the first two birthdays differ. If they were equal, the room would already contain a match and would not belong to the event being counted.

Check yourself

In the same model, find the probability that at least two of three people share a birthday. Compare it with $3/365$ , the sum of the match probabilities of the three pairs.

Show the answer

By the multiplication rule the three birthdays are all different with probability

\frac{364}{365} \cdot \frac{363}{365} = \frac{132132}{133225}.

By the complement rule a shared birthday has probability

1 - \frac{132132}{133225} = \frac{1093}{133225},

which is about $0.00820$ . The sum $3/365 = 1095/133225$ is about $0.00822$ , slightly larger. The sum counts the rooms in which all three people share one birthday three times instead of once. Those rooms have probability $1/365^2 = 1/133225$ , and counting them two extra times accounts for the difference of $2/133225$ .

Change the number of days. Suppose each person’s birth month is one of $12$ months, each with probability $1/12$ , independently of everyone else. What is the smallest group in which a shared birth month is more likely than not?

Show the answer

The same argument with $12$ in place of $365$ gives, for $4$ people,

\begin{aligned} &P(\text{all different}) \\[0.4em] &\quad = \frac{12 \cdot 11 \cdot 10 \cdot 9}{12^4} = \frac{55}{96}, \end{aligned}

so a shared month has probability $41/96$ , about $0.427$ . For $5$ people the extra factor $8/12$ gives

\begin{aligned} &P(\text{all different}) \\[0.4em] &\quad = \frac{55}{96} \cdot \frac{8}{12} = \frac{55}{144}, \end{aligned}

so a shared month has probability $89/144$ , about $0.618$ . The smallest such group has $5$ people, who form $10$ pairs. Real months have different lengths, so this equal chance model is again a simplification.

Now ask the narrower question. In the 365-day model, how many other people are needed before the probability that at least one of them shares your birthday is more than one half?

Show the answer

Each other person misses your birthday with probability $364/365$ , independently of the others, so with $m$ other people

\begin{aligned} &P(\text{a match with you}) \\[0.4em] &\quad = 1 - \left(\frac{364}{365}\right)^{m}. \end{aligned}

This is more than one half exactly when $(364/365)^m$ is less than one half. Taking natural logarithms, that means

\begin{aligned} m &> \frac{\ln 2}{\ln(365/364)} \\[0.4em] &\approx 252.65. \end{aligned}

So $253$ other people are needed. Checking directly, $252$ others give about $0.4991$ and $253$ others give about $0.5005$ . A common guess is about half of $365$ , but $183$ others give only about $0.395$ . Some of them are likely to share birthdays with one another, and then together they cover fewer than $183$ different days. By contrast, $23$ people are enough for a match between any two of them, and those $23$ people already form $253$ pairs, the same number of comparisons that your question needs.

The Birthday Paradox

Video 1, chapter 9

Key terms

Birthday problem

Number of pairs

Complement rule

Multiplication rule

Check yourself