Collisions: the birthday problem

The birthday problem is a famous probability puzzle: how many people must be in a room before it is more likely than not that two of them share a birthday? The answer surprises most people, and the method behind it applies well beyond birthdays.

We start with three people. How likely is it that no two of them share a birthday?

We take each person's birthday to be equally likely to fall on any of $365$ days, which is a close approximation to real birthdays.

An outcome lists the three birthdays in order, one per person, and a day can appear more than once. That is an ordered sample of size $3$ from $365$ days with replacement, so

No match means the three birthdays are all different. The first person can have any of $365$ days, the second any of the $364$ left and the third any of the $363$ left. That is the count of ordered samples without replacement, so

Nothing here depends on there being three people or $365$ days.

The same count applies whenever each of $k$ things is equally likely to land in any of $m$ places, such as people's birth months ($m = 12$). In that general setting, a match is called a collision.

Five people each pick a whole number from $1$ to $20$ at random, every number equally likely. Let $A$ be the event that no two people pick the same number. Write $P(A)$ as a ratio of counts.

Solution

Each person is equally likely to pick any number, so every outcome is equally likely and

Here $k$ counts the people and $m$ the numbers:

• $k = 5$ people.
• $m = 20$ numbers.

An outcome lists the number each of the five people picks, in order, and a number can be picked more than once, so:

The outcomes in $A$ are those where the five people pick five different numbers. The first person can pick any of the $20$ numbers, the second any of the $19$ left, and so on down to the fifth, who has $16$ left:

Dividing the second count by the first:

We've seen how to find the probability that no two people in a group share a birthday. A different question is how likely it is that someone shares one particular person's birthday, say Ana's.

Picture Ana in an empty room, with the others arriving one at a time. For no one to share Ana's birthday, each new arrival only has to avoid Ana's day, so every one of them has $364$ of the $365$ days available.

Suppose the group has $k$ people: Ana and $k - 1$ others. Ana's birthday is already set, so an outcome lists the birthdays of the $k - 1$ others, and

The bottom counts every outcome for the $k - 1$ others, and the top counts the outcomes in which each of them avoids Ana's day.

By the complement strategy,

Nothing here depends on birthdays. Each person is a draw from $365$ days and Ana's is the first, so the same count works for any ordered sample.

In words: each of the $k - 1$ later draws has $m - 1$ values out of $m$ that avoid the first draw's value, and a collision is the complement of all of them avoiding it.

Leo and three friends compare birth months, each equally likely to be any of the $12$ months. Find the probability that at least one friend shares Leo's month.

Solution

Every outcome is equally likely, so we find the probability that no friend shares Leo's month by counting outcomes.

Leo's month is fixed, so an outcome lists the months of the three friends, each one of $12$:

No friend shares Leo's month when each friend avoids that one month. Each friend has the same $11$ months left:

Dividing the second count by the first:

By the complement strategy,

Back to the puzzle: how many people does a room need before a shared birthday is more likely than not? More likely than not means a probability greater than $0.5$, so we want the smallest number of people $k$ for which $P(\text{at least one match}) > 0.5$.

How does a match between any two people compare with a match with Ana? By the complement strategy, $P(\text{at least one match}) = 1 - P(\text{no match})$. The graph shows it in blue for each number of people $k$, with a match with Ana in green.

A match between any two people passes $0.5$ at $k = 23$. In the same group, the chance that someone shares Ana's birthday is only about $0.06$.

Why the gap? To have no match with Ana, each new arrival only needs to avoid her one day, so every arrival has $364$ safe days. To have no match at all, each arrival must avoid every birthday already in the room, so the safe days shrink: $364$, then $363$, down to $343$ for the $23$rd person.

Zoe and four friends each spin a spinner with $10$ equal sections, numbered $0$ to $9$. Which is more likely: that at least one friend lands on Zoe's number, or that at least two of the five land on the same number?

Solution

For a match with Zoe, her number is fixed and each of the other $4$ people has $9$ numbers that avoid it:

For a match between any two of the five, no match means five different numbers. The first person has $10$ numbers, the second the $9$ left, and so on down to $6$ for the fifth:

By the complement strategy,

A match between any two of the five is about twice as likely, because it can come from any of the $\binom{5}{2} = 10$ pairs of people, not only the $4$ pairs that include Zoe.