2.5 The Birthday Problem

This is a famous problem in probability, which we address here in stages. We introduce a simple version, and make it more complex in steps until we can tackle the general problem.

Two People on April 3

Example 1 Let's imagine we have the case where two people meet on the street. What is the probability that they both have April 3 as their birthday?

Show solution

This can be solved with a straightforward application of the product rule, Equation 1.8 on page 42.

$A ≡ Person 1 has a birthday on, say, April 3; B ≡ Person 2 has a birthday on, say, April 3; P open parenthesis A and B close parenthesis equals P open parenthesis A vertical bar B close parenthesis P open parenthesis B close parenthesis$

Each of these terms can be calculated. Firstly, $P (A | B)$ is the probability that person 1 has a certain birthday given that person 2 has the same birthday. However, knowing the birthday of the second person doesn't tell us anything about the birthday of the first person, thus they are independent and $P (A | B) = P (A)$ .

Secondly, the probability of having any particular birthday is simply $P open parenthesis A close parenthesis equals 1 / 365$ . Finally, we have

$\begin{matrix} A \equiv Person 1 has a birthday on, say, April 3 \\ B \equiv Person 2 has a birthday on, say, April 3 \\ P (A and B) = \frac{1}{365} \times \frac{1}{365} = \frac{1}{133, 225} = 0.0000075 \end{matrix}$

which is extremely unlikely (see Table 1.1 on page 51)!

Two People

Example 2 Two people meet on the street, and we ask what is the probability that they both have the same birthday?

Show solution

How is this different than the previous question, where we specified which birthday they had? Our intuition immediately suggests that this probability must be higher than the previous one, because there are more possibilities - rather than April 3, they could be born on January 1 or May 3 or any other day. Using our notation we have the following definitions:

$C sub 1 ≡ Person 1 and Person 2 both have a birthday on January 1; C sub 2 ≡ Person 1 and Person 2 both have a birthday on January 2; ⋮; C sub 365 ≡ Person 1 and Person 2 both have a birthday on December 31$

and the probability we are looking for is

$P open parenthesis C sub 1 or C sub 2 or ⋯ or C sub 365 close parenthesis$

In this situation we can note that these are exclusive statements. For example, it can't be true that both $C sub 1$ and $C sub 2$ are true - you can't have more than one birthday. Thus, the Sum Rule (Equation 1.10 on page 1.10) reduces to the Limited Sum Rule (Equation 1.11). Further, each term in that rule is the same

$\begin{matrix} P (C_{1}) = P (C_{2}) = \dots = P (C_{365}) = \frac{1}{365} \times \frac{1}{365} \end{matrix}$

so we have

$\begin{matrix} P (C_{1} or C_{2} or \dots or C_{365}) = \\ \underset{365 terms, one for each day}{\underset{⏟}{(\frac{1}{365} \times \frac{1}{365}) + (\frac{1}{365} \times \frac{1}{365}) + \dots + (\frac{1}{365} \times \frac{1}{365})}} \\ = \frac{1}{365} = 0.0027 \end{matrix}$

Another way to think of this is to imagine that person 1 randomly “chooses” their birthday, $D sub 1$ , and person 2 randomly “chooses” their birthday, $D sub 2$ , and then they compare to see if the days are the same, or $D sub 1 equals D sub 2$ . In general, we can think of the problem broken up in this way:

$\begin{matrix} P (D_{1} = D_{2}) = \\ P (D_{1} is a specific day and D_{2} is the same day) \times (number of possible specific days) \end{matrix}$

In this way, we get

$\begin{matrix} P (D_{1} = D_{2}) = (\frac{1}{365} \times \frac{1}{365}) \times (365) \\ = \frac{1}{365} = 0.0027 \end{matrix}$

which is extremely unlikely (see Table 1.1 on page 51), but not nearly as unlikely as them both having the same April 3 birthday.

Three People

Example 3 What is the probability that three random people have the same birthday?

Show solution

Going through the same logic, we have

$\begin{matrix} P (D_{1} = D_{2} = D_{3}) = (\frac{1}{365} \times \frac{1}{365} \times \frac{1}{365}) \times 365 \\ = \frac{1}{133, 225} = 0.0000075 \end{matrix}$

which is even more extremely unlikely (see Table 1.1 on page 51) than the previous two-person example. It is interesting to note that this is the same answer we received when we asked for the probability of two people with a specific birthday. One can think of the three people having the same, unspecified, birthday in the following way if it helps. The first person's birthday specifies the necessary birthday for the other two, so it is the same as the case where we specify a single birthday for two people.

Two People...Out of Three

Usually, we don't have a situation where we have random people meeting and all agreeing on birthdays. What we have is a group of people talking, and two people in the group end up saying “Hey, my birthday is April 3 too!” This is quite a bit different, and leads to some unintuitive consequences. Let's go through the situation with three people, and we ask the question

Example 4 What is the probability that at least two have the same birthday?

Show solution

Writing this out we get (somewhat messily)

$\begin{matrix} P (at least two out of three have the same birthday) = \\ = P (exactly 2 the same or exactly 3 the same) \\ = P (exactly 2 the same) + \\ \underset{{(\frac{1}{365})}^{3} \times 365}{\underset{⏟}{P (exactly 3 the same)}} - \underset{0}{\underset{⏟}{P (exactly 2 and exactly 3 the same)}} \end{matrix}$

The term $P open parenthesis exactly 2 the same close parenthesis$ can be broken up like

$\begin{matrix} P (exactly 2 the same) = P (a specific 2 are the same) \times (number of possibilities of 2 the same) \\ = P (D_{1} = D_{2} and not D_{1} = D_{3}) \times (number of possibilities of 2 the same) \end{matrix}$

Applying the product rule we get

$\begin{matrix} P (exactly 2 the same) = \\ = P (D_{1} = D_{2} and not D_{1} = D_{3}) \times (number of possibilities of 2 the same) \\ = P (D_{1} = D_{2} | not D_{1} = D_{3}) P (not D_{1} = D_{3}) \times (number of possibilities of 2 the same) \\ = \underset{\frac{1}{365}}{\underset{⏟}{P (D_{1} = D_{2})}} \underset{\frac{364}{365}}{\underset{⏟}{P (not D_{1} = D_{3})}} \times (number of possibilities of 2 the same) \end{matrix}$

Noting that there are 3 ways of getting a specific 2 the same, we obtain for this single term

$\begin{matrix} P (exactly 2 the same) = \frac{1}{365} \times \frac{364}{365} \times 3 \end{matrix}$

Putting it all together we have

$\begin{matrix} P (at least two out of three have the same birthday) = \\ = P (exactly 2 the same or exactly 3 the same) \\ = \frac{1}{365} \times \frac{364}{365} \times 3 + {(\frac{1}{365})}^{3} \times 365 \\ = 0.0082 \end{matrix}$

Example 5 What is the probability that at least two have the same birthday? A clever shortcut.

A clever way of rethinking this problem, which significantly reduces the calculations, is found by asking the following question: in a group of people, what is the probability that none of the people have the same birthday? This can be approached in a step-wise fashion. Person 1 “chooses” a birthday, out of 365 they have all 365 possibilities. Person 2 “chooses” their birthday, with probability $P equals 364 / 365$ of not being the same as Person 1. Person 3 now has 363 “choices” out of 365 to avoid both other birthdays, etc... So the probability of using this process and getting to Person 3 and not have any overlapping birthdays is simply

$\begin{matrix} P (none the same in 3 people) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \end{matrix}$

Now, if we're interested in the probability that at least two are the same, then this is the exact opposite of the probability that none are the same. Using the Negation Rule (Equation 1.7 on page 41) we have

$\begin{matrix} P (none the same in 3 people) + P (not ``none the same in 3 people'') = 1 \\ P (none the same in 3 people) + P (at least 2 the same in 3 people) = 1 \end{matrix}$

which leads to

$\begin{matrix} P (at least 2 the same in 3 people) = 1 - P (none the same in 3 people) \\ = 1 - \frac{364}{365} \times \frac{363}{365} \\ = 0.0082 \end{matrix}$

Two People...Out of Thirty

Example 6 When you have a group of 30 people, like students in a classroom, and you ask what the probability of finding two in the room with the same birthday, would your intuition say it is greater or less than 50%?

Show solution

Many people find that their intuition suggests reasonably strongly that it would be less than 50%. We can now do this problem quite easily, and we find that our intuition does not match. Following the same procedure as with 3 people, we imagine each person “choosing” their birthday with a dwindling selection as we go on to avoid “choosing” one that has already been taken. The probability that no one in the room has the same birthday as any other is

$\begin{matrix} P (none the same in 30 people) = \underset{30 terms}{\underset{⏟}{\frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \cdot \times \frac{336}{365}}} \\ = 0.29 \end{matrix}$

So the probability of having at least 2 people in the room having the same birthday is

$\begin{matrix} P (at least 2 the same in 30 people) = 1 - 0.29 \\ = 0.71 \end{matrix}$

which is 71%! Compare this likely outcome to the extremely rare outcome of having two random people having matched birthdays, from page 58. See Figure 2.2 to see a plot of this unintuitive observation.

Figure 2.2. Probability of having at least two people in a group with the same birthday depending on the number of people in the group. The 50% mark is exceeded once the group size exceeds 23 people.

Adapted from Statistical Inference for Everyone, by Brian Blais (Bryant University), licensed under CC BY-SA 4.0 (dual-licensed under the GNU FDL 1.2 or later; this adaptation uses the CC BY-SA grant). Changes were made; this adaptation is distributed under the same license. License: CC-BY-SA-4.0.