Tag: the birthday problem

We recently completed a round of interviews for a senior data scientist to join the Data Mettle team (welcome aboard Ying!)

Anyone who has recruited senior data scientists knows it’s a complex role to hire for. Even for a team of senior data scientists. Candidates need to have skills across coding and engineering, as well as statistics.

To get a sense of a candidate’s maths abilities, we’ve taken to asking them the birthday problem question.

If you aren’t familiar: the birthday problem, or birthday paradox, addresses the probability that any two people in a room will have the same birthday. The paradox comes from the fact that you reach 50 per cent likelihood two people will share a birthday with just 23 people in a room. With 70 people you get to 99.9% likelihood.

So, during our interview process, we ask the candidate to work through this problem by simply asking, “If you have N people in a room, how likely are they to share a birthday with each other”?

Stated otherwise, Given \(n\) people in a room, what is the probability \(P(A_n)\) that two or more of them have the same birthday? We like this problem since it shouldn’t take much longer than 15-20 minutes to solve given a reasonable background in statistics, along with some helping pointers from us.

I does have one big flaw though, and that is that \(P(A_n)\) is very complicated to calculate directly. Instead, the trick to solving the problem is to look at the complement \(P(A’_n)\): What is the probability that no two people share their birthday? This is reasonably straightforward to calculate, and \(P(A_n)\) is readily calculated from \(P(A’_n)\) as \(P(A_n) = 1 – P(A’_n)\).

Very few candidates that we interviewed actually thought of this trick, and instead attempt to plow ahead solving it as stated. But, once they get stuck we drop this hint and it generally leads to a breakthrough.

Now that our round of interviews are complete, we wanted to explore this problem in greater detail, and share the underlying mathematics that helps us solve the birthday problem.

We’ll explain the solution with the standard trick, but we’ll also attempt to solve it without considering the trick, which turns out to be a very interesting (and complex) combinatorial problem in its own right.

Note: we assume all days equally probable, and no leap year

The Standard Candidate Solution

Most candidates need a bit of help getting started, so we usually suggest considering the situation for two people, \(P(A_2)\). Let’s call them Alice and Bob.

The probability that Alice and Bob have the same birthday is fairly straightforward to calculate. Simply take Alice’s birthday as given, then the probability of Bob also having the same birthday is \(1/365\).

However, to set things up for what follows, we’ll express this probability slightly differently. First if we consider Alice in isolation, ignoring Bob, her birthday can fall on any day of the year, so the probability of her having a unique birthday (ignoring Bob for now) is \(365/365\). Now Bob’s birthday has to fall on the same day as Alice’s, and the probability for that is \(1/365\), which gives us
\[
P(A_2) = \frac{365}{365}\cdot\frac{1}{365}.
\]

Now let’s move to the case of 3 people, \(P(A_3)\). Meet Carol.

At this point, a few candidates blurt out “1/365²”, which is usually a warning sign that they are at a loss for how to proceed. This is where things start getting complicated. We need to carefully consider the various possible cases (in the pictures to the left people stacked on top of each other share the same birthday):

I. They all have different birthdays,

II. Alice & Bob share the same birthday, while Carol has a different birthday,

III. Alice & Carol share the same birthday, while Bob has a different birthday,

IV. Bob & Carol share the same birthday, while Alice has a different birthday,

V. Alice, Bob and Carol all have the same birthday.

As these are disjoint events, we can see that

\begin{align}
P(A_3) &= P(\textrm{either event II-V occurs}) \\
&= P(\textrm{event II occurs}) \ + \\
&\phantom{==} P(\textrm{event III occurs}) \ + \\
&\phantom{==} P(\textrm{event IV occurs}) \ + \\
&\phantom{==} P(\textrm{event V occurs}).
\end{align}

We can also note that the probability of either event II, III or IV happening are all equal, so we can simplify this further:

\begin{align}
P(A_3) &= P(\textrm{either event II-V occurs}) \\
&= 3P(\textrm{event II occurs}) \ + \\
&\phantom{==} P(\textrm{event V occurs}).
\end{align}

However, this is where it starts getting a bit hairy, and generalising this approach for more people quickly gets very complex (as we’ll see in a bit). Instead, at this point we indicate that perhaps there’s a better way, which usually leads the candidate to realise that

\[
P(\textrm{either event II-IV occurs}) = P(\textrm{event I does not occur}) = 1 – P(\textrm{event I occurs}),
\]

i.e. \(P(A_3) = 1 – P(A’_3)\).

So, let’s turn our attention to \(P(A’_3)\), that is, Alice, Bob and Carol all have different birthdays. Following the same approach as when calculating \(P(A_2)\), we have that

• Alice’s birthday can fall on any day of the year (probability \(365/365\)),
• Bob’s birthday has to fall on any day other than Alice’s birthday (probability \(364/365\)), and
• Carol’s birthday has to fall on any day other than Alice’s and Bob’s birthday (probability \(363/365\)).

So all in all,
\[
P(A’_3) = \frac{365}{365}\cdot\frac{364}{365}\cdot\frac{363}{365}.
\]

This line of reasoning is easily extended to n people, which leads to

\[
P(A’_n) = \frac{365}{365}\cdot\frac{364}{365}\cdots\frac{365-n+1}{365} = \frac{365!}{(365-n)!\cdot 365^n},
\]

and finally we arrive at the answer:

\[
P(A_n) = 1\, -\, P(A’_n) = 1\, -\, \frac{365!}{(365-n)!\cdot 365^n}.
\]

The hard way

How do we calculate this without using the trick? If we stick to the case where \(n=3\) for a moment, it’s fairly straightforward to calculate \(P(\textrm{event II occurs})\) and \(P(\textrm{event V occurs})\), following the same argument as above. For event II, we have that:

• Alice’s birthday can fall on any day of the year (probability \(365/365\)),
• Bob’s birthday has to fall on Alice’s birthday (probability \(1/365\)), and
• Carol’s birthday has to fall on any day other than Alice’s and Bob’s joint birthday (probability \(364/365\)),

so \(P(\textrm{event III occurs}) = 364/365^2\). For \(P(\textrm{event V occurs})\), they all need to have the same birthday, and the chance of this happening is
\(1/365^2\). So all in all,
\[
P(A_3) = 3\frac{364}{365^2} + \frac{1}{365^2}.
\]

Note that we should have \(P(A_3) + P(A_3′) = 1\), which is indeed true. For those interested, this is shown in the Appendix below.

Let’s turn to the general case of n people. Now the number of cases quickly gets very complicated. For illustration, in the case of 4 people (introducing Dan) there are 15 different cases (again, people stacked on top of each other share the same birthday):

With 5 people there’s 52 cases, with 6 people there’s 203 cases and so on, growing very rapidly. With 23 people there are over \(4\cdot 10^{16}\) cases!

Note that the 15 events for 4 people come if 5 distinct “shapes”:

• No-one shares their birthday with anyone else (1 event),
• Two people share their birthday, and the other two have their own birthdays (6 events),
• Two people share their birthday, and the other two also share their birthday (3 events),
• Three people share their birthday, and the remaining do not (4 events),
• All four people have the same birthday (1 event).

Two key observations are that all events of the same shape have the same probability, and that a shape is conveniently captured by the mathematical concept of a partition of a number \(n\).

Partitions and multinomial coefficients

A partition of a number \(n\) is simply one way of writing it as a sum of positive numbers:
\[
n = a_1 + a_2 + \cdots + a_k.
\]
For example, there are five partitions of the number four,
\begin{align}
4 &= 1 + 1 + 1 + 1, \\
4 &= 2 + 1 + 1, \\
4 &= 2 + 2, \\
4 &= 3 + 1, \\
4 &= 4,
\end{align}
each corresponding to a specific shape above (i.e. \(2 + 1 + 1\) corresponds to the third case, where two people share their birthday, and the other two have distinct birthdays). Partitions are usually denoted by the Greek letter \(\lambda\), where \(\lambda\vdash n\) means that \(\lambda\) is a specific partition of the number \(n\). If we let \(N(\lambda)\) denote the number of events of shape \(\lambda\), let \(P(\lambda)\) denote the probability of a specific event of shape \(\lambda\) happening, and \(\max(\lambda)\) be the maximum term in the partition, we can write \(P(A_n)\) as
\[
P(A_n) = \mathop{\sum_{\lambda\vdash n}}_{\max(\lambda) \geq 2} N(\lambda)P(\lambda).
\qquad\qquad\textrm{(1)}
\]
Note that the sum runs over all partitions except \(n = 1 + \cdots + 1\), which corresponds to the unique event of everyone having separate birthdays.

We begin by working out \(P(\lambda)\), as it’s the easier to handle. As it turns out, \(P(\lambda)\) depends only on the “length” of the partition, i.e. the number of days covered by birthdays. Instead of proving this rigorously we’ll show it by example. Let’s look at two different cases that cover two days. First consider Alice and Bob sharing birthdays, and Carol and Dan sharing birthdays:

• Alice’s birthday can fall on any day of the year (probability \(365/365\)),
• Bob’s birthday has to fall on Alice’s birthday (probability \(1/365\)), and
• Carol’s birthday has to fall on any day other than Alice’s and Bob’s joint birthday (probability \(364/365\)),
• Dan’s birthday has to fall on Carol’s birthday (probability \(1/365\)),

so the probability of this happening is:
\[
\frac{365}{365}\cdot\frac{1}{365}\cdot\frac{364}{365}\cdot\frac{1}{365}
=
\frac{365\cdot 364}{365^4}.
\]
Now consider Alice, Bob and Carol sharing birthdays, with Dan having his birthday on a different day:

• Alice’s birthday can fall on any day of the year (probability \(365/365\)),
• Bob’s birthday has to fall on Alice’s birthday (probability \(1/365\)),
• Carol’s birthday has to fall on Alice’s and Bob’s shared birthday (probability \(1/365\)), and
• Dan’s birthday has to fall on any day apart from Alice’s, Bob’s and Carol’s shared birthday (probability \(364/365\)),

so the probability of this happening is:
\[
\frac{365}{365}\cdot\frac{1}{365}\cdot\frac{1}{365}\cdot\frac{364}{365}
=
\frac{365\cdot 364}{365^4}.
\]
Note in particular that the left hand side of both expressions have the same factors, just in a different order. Whenever we add someone sharing their birthday with the previous person, we add a factor \(1/365\), and whenever we add someone who has a “new” birthday we add a factor:

\[
\frac{365 – \textrm{number of days already covered}}{365}.
\]
So, in general, if an event covers \(k\) days, the probability of it occurring is
\[
\frac{365!}{(365-k)!365^n}.
\]
If we let \(\operatorname{length}(\lambda)\) denote the length of \(\lambda\), this means that
\[
P(\lambda) = \frac{365!}{(365-\operatorname{length}(\lambda)!365^n}.\qquad\qquad\textrm{(2)}
\]

Now all that is left is to figure out what \(N(\lambda)\) is. We can think of this as “how many ways can we fill the shape with people?”. The multinomial coefficients tell us exactly that! For a partition \(\lambda = a_1 + \cdots + a_k\) they are defined as
\[
\binom{n}{\lambda} = \binom{n}{a_1, \dots, a_k} = \frac{n!}{a_1!\cdots a_k!}.
\]

For example, for the partition \(4 = 2 + 2\) we have
\[
\binom{4}{2, 2} = \frac{4!}{2!\cdot 2!} = \frac{1\cdot 2\cdot 3\cdot 4}{1\cdot 2\cdot 1\cdot 2} = 6,
\]
so there are 6 ways to fill in the corresponding shape:

Hm, this doesn’t seem right, do we not have 3 cases of this shape above? Indeed we do! This way of “filling in the shape” actually counts the same event several times. Note that the first and fourth both correspond to Alice and Bob sharing birthdays, and Carol and Dan sharing birthdays, the two days are simply swapped. Each event in the top row is the same as the event below it. So, how do we fix this?

The problem is that the filling in method distinguishes between days in a way that we don’t want to do. We don’t care which specific day peoples birthday fall on. Whenever we have two or more days that have the same number of people sharing birthdays on those days, we count that as one case, whereas the corresponding multinomial coefficient counts all possible ways we can permute those days. To deal with this, we need to consider the length of runs of equal terms in a partition. For example, the partition
\[
7 = 2 + 2 + 1 + 1 + 1 = 2 \cdot 2 + 3 \cdot 1
\]
has one run of length \(2\) (the two 2’s) and one run of length \(3\) (the three 1’s).

To formalise this, for a permutation \(\lambda \vdash n\) we can collect equal terms and write it as
\[
n = c_1b_1 + \cdots + c_mb_m,
\]
where \(b_1 > b_2 > \cdots > b_m\). Then the numbers \(c_1\), \(c_2\), …, \(c_m\) are the lengths of all the runs of equal terms in our partition. We can now define \(s(\lambda)\), which counts the number of ways we can swap days in a shape while still being in the same event, as
\[
s(\lambda) = c_1!\cdots c_m!
\]

With all this machinery in place we’re finally in a place to write out the full formula for \(P(A_n)\). As \(s(\lambda)\) accounts for the “double counting” of the multinomial coefficients, we have that
\[
N(\lambda) = \binom{n}{\lambda} / s(\lambda). \qquad\qquad\textrm{(3)}
\]
Substituting the expressions (2) and (3) for \(P(\lambda)\) and \(N(\lambda)\) into Equation (1) above gives us
\[
P(A_n) = \mathop{\sum_{\lambda\vdash n}}_{\max(\lambda) \geq 2} \binom{n}{\lambda}\cdot\frac{365!}{(365-\operatorname{length}(\lambda))!365^ns(\lambda)}.
\]

Lovely, isn’t it?

Since we’ve done all this work, it’s worth noting that, as the number of partitions of a number \(n\) grows with \(\tilde e^{\sqrt{n}}\), the computational complexity of calculating this formula is exponential in \(n\). This should be contrasted with the linear complexity of the “trick” solution. On the other hand, this more complex solution is easy to adapt to answer more complex questions, like “what is the probability that no three people share the same birthday”.

Finally

The birthday problem isn’t intuitive right away – the idea that only 23 people need to be present to have a coinflip’s chance that two people share the same birthday. Solving this paradox is even less intuitive. If you’ve read this far though, you’ll surely nail your next interview for a data scientist position at Data Mettle.

And next time you go to a birthday party with more than 70 people just remember, you are probably forgetting to say happy birthday to at least one person.

Appendix

If you’ve made it this far, The fact that \(P(A_3) + P(A_3′) = 1\) can be seen by rearranging the terms:
\begin{align}
P(A_3) + P(A_3′)
&=
3\frac{1}{365}\cdot\frac{364}{365} + \frac{1}{365^2} + \frac{364}{365}\cdot\frac{363}{365} \\
&=
\frac{3\cdot 364 + 1 + 364\cdot 363}{365^2} \\
&=
\frac{364 + 1 + 2\cdot 364 + 363\cdot 364}{365^2} \\
&=
\frac{365 + (2 + 363)\cdot 364}{365^2} \\
&=
\frac{365\cdot 1 + 365\cdot 364}{365^2} \\
&=
\frac{365^2}{365^2} \\
&=
1.
\end{align}

Icons made by Freepik from www.flaticon.com.