Is it Anyone’s Birthday?
Probability ; Difficulty: medium
The Riddler Express Mar 18 '22: Is it Anyone's Birthday
This week’s Riddler Express deals with the age old “So whose birthdays are we celebrating on the office team this month” question. I don’t usually post solutions to the Express but this one has an extra credit that I found interesting. Here’s the puzzle with the important extra credit part:
Earlier today, James’s boss was surprised to find out that not only did no one on their team have a birthday this week, but that nobody was celebrating a birthday for the entire month. With a total of 40 people on the team, the probability of this happening seemed to be miniscule.
But was that really the case? What was the probability that none of the 40 people had birthdays this month? (For the purpose of this riddle, assume that a year consists of 12 equally long months. It’s a sufficiently good approximation!)
Extra credit: What is the probability that there is at least one month in the year during which none of the 40 people had birthdays (not necessarily this month)?
*spoiler alert* solution and answer follow below
Easy part 1
We’re really here for the extra credit. So let’s get the first part out of the way ASAP.
With the assumption of 12 equally long months, we are being asked to calculate the probability that none of the 40 employees have a birthday in a given specific month (Mar). The probability that a given employee doesn’t have a birthday in March i.e has a birthday in one of the other 12 months is \( \frac{11}{12} \) . So the probability that none of the 40 employees have a March birthday (or a birthday in any one given month) is :
\[
\left (\frac{11}{12} \right )^{40} = 0.0308 \text{ or } {\color{Red} {3.08 \%}}
\]
This is indeed quite low and worthy of the Boss’ surprise since there is an almost 97% chance of having a birthday in March!
The interesting extra credit problem:
Let’s first calculate the probability that all months have at least one birthday. The required answer is then just 1 minus this number. Now this exercise is simple if you’re familiar with the curiously named Stirling Numbers of the Second Kind. But let’s assume you are not and want to hack at this from first principles:
Let \(C_{n,k}\) represent the number of different ways that \(n\) people’s birthday’s can be assigned to \(k\) different months such that each month has at least one person’s birthday fall in that month . This can also be thought of as \(n\) distinguishable balls in \(k\) distinguishable urns with each ball having an equal probability of being in any of the \(k\) urns and each urn having at least 1 ball . We want to calculate \(C_{40,12}\).
Calculating \(C_{n,k}\) directly is not easy. But we can easily recognize a few identities that will help us calculate it.
Firstly, when you have \(n\) balls and \(n\) urns, each urn has to contain exactly 1 ball for there to be at least 1 ball in each:
\[
C_{n,n} = n!
\]
Second, if there was only one urn, there’s obviously only 1 way to assign the \(n\) balls. So:
\[
C_{n,1} = 1
\]
Third and most importantly we have the following recursive relation:
\[
C_{n+1,k} = k\cdot C_{n,k} \ \ + \ \ k\cdot C_{n,k-1}
\]
This is because when you add a new distinguishable ball to the existing \(n\) balls, one of two things has to be true in any final set of permutations:
i. we have the existing permutations, and the new ball is placed in any one of the \(k\) urns. There are \(k\) ways to do this.
ii. The new ball is the sole member of one of the \(k\) urns. This can again be done in k ways with the other \(n\) balls arranged in the \(k-1\) urns in \(C_{n,k-1} \) ways.
The total number of ways is just the sum of the two resulting terms above.
With these, it is possible to recursively calculate \(C_{40,12}\). Easily done with a few lines of code (included below). The answer turns out to be:
\(9894740006730707433667391906947423146393600\) or roughly \(9.89 \times 10^{42}\) possibilities such that each month has at least one of the 40 birthdays falls in it.
It is important to note that each of these possibilities is equally likely (with probability \(\left (\frac{1}{12} \right )^{40}\) )
The total number of possibilities of assigning 40 birthdays to 12 months (without any restrictions) is simply:
\( 12^{40} = 14697715679690864505827555550150426126974976\) or roughly \(14.7 \times 10^{42}\)
The required probability is then:
\begin{align*}
& 1 \ – \ \frac{C_{40,12}}{12^{40}} \\ \\
&=\frac{4802975672960157072160163643203002980581376}{14697715679690864505827555550150426126974976} \\ \\
&= \mathbf{{\color{Red} {0.3268 \text{ OR } 32.68\% } }}
\end{align*}
32.68% is a surprisingly large number for the probability that a 40 person team will go at least one month without celebrating a birthday!
To ensure the answer is correct, I ran a quick simulation 1 M times to get 326887 times with at least one birthday free month or 32.69%— in agreement with the calculated answer.
Observations:
- Our answer is more than 10 times the probability that there is no birthday this month. How should we understand the difference? Here’s one way to think about it: say you have loaded coin such that the probability of getting heads on any given throw is 3.08% (same as our March birthday absence probability). If we were to throw this coin 12 times, our chances of getting at least 1 head in those 12 throws is going to be considerably higher than the probability of getting heads on a particular single throw. In fact the chance of getting at least 1 heads is 31.3% which is not too different from our answer of 32.7%.
- The probability of having at least one birthday free month obviously decreases with increasing number of employees. With 11 or fewer employees, it is obviously 100%. With 12 it is 99.99% ; 25 it is 81.8%, 30 it is 64. 1% , 40 it is 32.68%. and at 50 it drops to 14.7%.
Python Code to calculate number of possibilities \(C_{n,k}\):
from math import factorial
def get_comb(n,k):
if n == k :
result = factorial(k)
elif k == 1 :
result = 1
else :
result = k*get_comb(n-1,k) + k*get_comb(n-1,k-1)
return result
num_people = 40
num_months = 12
num_possibilities = get_comb(num_people,num_months)
print("number of possibilities = ", num_possibilities)
print("required probability = ", 1 - num_possibilities/num_months**num_people)