The birthday-cake problem: a variation on the birthday problem

655 Views Asked by At

Suppose we randomly select 100 people and record each of their birthdays. (Assume a year of 365 days, and an equal chance of being born on any of them.) Suppose further that over the course of a year, we buy a birthday cake on each day when any of those 100 people (one or more) has a birthday.

It's possible, though unlikely, that no two people among the 100 share a birthday, in which case we'd end up buying 100 cakes. It's also conceivable, though extremely unlikely, that all 100 people share the same birthday, in which case we'd buy just one cake.

The question is: in the given scenario, what is the most likely number of cakes we will end up buying over the course of a year?

More generally, how would we go about making a similar calculation for $n$, the number of days on which at least $a$ people, from a group of $b$ members, has a birthday, in a year of $c$ days? How could we describe the probability distribution of $n$ over the range of $[0,$ min$(b, c)]$?

1

There are 1 best solutions below

3
On

I'll consider the general problem with $a=1$. Consider a given set $S$ of $s$ days, $s \ge 0$. The probability that nobody has a birthday in the set $S$ is $(1-s/c)^b$. By the inclusion-exclusion principle, the probability that $S$ is exactly the set of days on which nobody has birthdays is $$ \sum_{T: S \subseteq T} (-1)^{|T|-|S|} \left(1 - \frac{|T|}{c}\right)^b = \sum_{i=0}^{c-s} (-1)^i {c-s \choose i} \left(1-\frac{s+i}{c}\right)^b $$ so that for $1 \le m \le \min(b,c)$ $$ \mathbb P(n = m) = {c \choose m} \sum_{i=0}^m (-1)^i {m \choose i} \left(\frac{m-i}{c}\right)^b$$

In the case $c=365$, $b=100$, the maximum occurs at $m = 88$: $\mathbb P(n=88) \approx .1348788529$. Unsurprisingly, this is very close to the mean, which is much easier to calculate: $365 - 365(364/365)^{100} \approx 87.57551806$.