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

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)]$?

• I bet, the distribution of the number of cakes tends to a Poisson distibution. – Édes István Gergely Apr 12 '16 at 20:55
• Note that the number of people in the survey group need not be fewer than the number of days in a year. For example, we could gather 400 people, even though a year has only 365 days, and yet the most likely number of resulting birthday cakes would intuitively seem almost certain to be less than 365. I suppose another interesting corollary of this problem is, given a 365-day year, what is the minimum number of people in the survey group required to make 365 the most likely number of birthday cakes bought? – jdmc Apr 12 '16 at 22:12

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$.
• Nicely done! You're right, asking how many days have one or more birthdays is really equivalent to asking how many days have no birthdays. Ah, but what if $a>1$? – jdmc Apr 12 '16 at 22:27