Possibility that there is a week where everyday someone has birthday (among 250 people)

combinatoricsstochastic-calculus

Why do I ask?

This is no homework of mine. Therefore, I don't need an answer as fast as possible. I ask out of curiosity. Hence, I am more interested in if my attempt is fine or where it goes wrong. I also don't need an exact final answer. It is sufficient to get an approximately correct answer. (For this question something like $1-10^{-500}$ is so close to $1$ that $1$ is good enough)

Question:

Assume there are $n=250$ people. How probable is it that there is (at least) one week such that every day of the week is a birthday.

Further, the year has $52$ weeks and $52\cdot7=364$ (for simplification) days per year.

My attempt:

First, I consider the probability that there is a week such that at least $7$ people have a birthday. This seems to be almost sure, because:

  • There are $364^{250}$ possible ways to distribute the birthdays over the year.
  • To get the number of possible ways such that each week has at most $6$ birthdays, I think of an urn where we have balls with numbers $1,\ldots,52$, and each ball appears $6$ times in the container. In total, we have $6\cdot 52=312$ balls, and all 250 people draw without putting back. There should be $\begin{pmatrix}312\\250\end{pmatrix}$ ways to do so.

Together I get:
\begin{align*}
P(\text{at least 7 birthdays per week}) &= 1-\frac{\begin{pmatrix}312\\250\end{pmatrix}}{364^{250}}>1-\frac{364^{60}}{364^{250}}>1-364^{-190}\\
&>1-6\cdot10^{-484}
\end{align*}
That is so close to $1$ that we assume that it is sure to have a week with at least $7$ birthdays.

Next, we have $m\geq 7$ birthdays for a week.

  • There are $\begin{pmatrix}k+7-1\\7-1\end{pmatrix}=\begin{pmatrix}k+6\\6\end{pmatrix}$ possible ways to put $k$ birthdays to $7$ days. Now, we take 7 birthdays and put each on one day of the week. The remaining $m-7$ birthdays are distributed in
    $$
    \begin{pmatrix}(m-7)+6\\6\end{pmatrix}=\begin{pmatrix}m-1\\6\end{pmatrix}
    $$
    ways. Hence, we get
    $$
    P_m(\text{each day is a birthday}) = \frac{\begin{pmatrix}m-1\\6\end{pmatrix}}{\begin{pmatrix}m+6\\6\end{pmatrix}} = \frac{(m-1)\cdot\ldots\cdot(m-6)}{(m+6)\cdot\ldots\cdot(m+1)}
    $$

My insight:

  • I'm not quite sure if my first step is correct. It is plausible that the probability has to be very high because there the average is around $\frac23$ birthdays per day. But the result seems to be a bit strange.

  • My second step is plausible to me. It is necessary to have $m>6$, and for increasing $m$, the probability goes to $1$.

But here I stuck:
I have a probability of having a week with $m>6$ birthdays, and I know $P_m(\text{each day of the week is a birthday})$, but I have no idea how to combine this information. I am just sure that I have to use the bounds $7\leq m\leq 250$ somehow.

I appreciate each help. Thanks a lot!

Best Answer

There are $364^{250}$ equally likely possibilities without restriction.

Counting possibilities where every week has at least one missing day, let us approach with generating functions.

$$\underbrace{\left(\underbrace{(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\overbrace{\dots+\frac{x^k}{k!}+\dots}^{k~\text{people born on this day}})}_{\text{monday}}\underbrace{(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots)}_{\text{tuesday}}\cdots\right)}_{\text{first week}}\underbrace{\left(\cdots\right)}_{\text{second week}}\cdots$$

Taking the generating function for the first week and calling that $W(x)$, the above generating function simplifies to be $W(x)^{52}$. The number of ways of distributing $K$ people would be $K!$ times the coefficient of $x^{K}$ in the expansion of the above.

This generating function, which when evaluated simplifies to $e^{364x}$, would have counted the number of ways to distribute the people among the days (with people distinct and so still each outcome is equiprobable). We look at $250!$ times the coefficient of $x^{250}$ here and one can show that this would have been precisely $364^{250}$ via the multinomial theorem.

Now, let us start modifying this... We want to remove the possibility of all days in a week occurring. We could do this by running inclusion-exclusion, but inclusion-exclusion over seven sets gets tedious to write out. Perhaps it might be preferable to break into cases here based on the earliest day in the week who didn't have anyone born on it. The only thing we'll need to modify is the generating function for each individual week as the same changes can be applied to all weeks.

$$\overbrace{\underbrace{1}_{\text{monday}}\underbrace{(1+x+\frac{x^2}{2!}+\dots)}_{\text{tuesday}}\underbrace{(1+x+\frac{x^2}{2!}+\dots)\cdots}_{\text{wednesday}}}^{\text{earliest missing: monday}}+\overbrace{\underbrace{(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots)}_{\text{monday}}\underbrace{1}_{\text{tuesday}}\underbrace{(1+x+\frac{x^2}{2!}+\dots)\cdots}_{\text{wednesday}}}^{\text{earliest missing: tuesday}}+\dots$$

Rewriting in terms of $e^x$, our modified week generating function:

$$W'(x)=e^{6x}+(e^x-1)e^{5x}+(e^x-1)^2e^{4x}+\dots+(e^x-1)^5e^x+(e^x-1)^6$$

The probability then that every week had at least one missing day when talking about $250$ people would be $250!$ times the coefficient of $x^{250}$ in the expansion of $W'(x)^{52}$ divided by $364^{250}$.

The probability that at least one week had all days represented would be $1$ minus that probability. The numbers unfortunately are far too large for me to get a numerical result with using the tools I have immediately available to me.

For a very loose estimate, we can look at the expected number of weeks such that all days in the week have at least one birthday. The probability that every day is present in the first week would be $1$ minus the probability that at least one day was absent. We can do this with inclusion exclusion.

$$1 - \dfrac{\binom{7}{1}363^{250}-\binom{7}{2}362^{250}+\binom{7}{3}361^{250}\pm\dots+\binom{7}{7}357^{250}}{364^{250}}\approx .0072$$

The expected number of weeks then with all dates having a birthday would be $\approx 52\times.0072\approx .3744$. This is technically an expected value, not a probability, but it does still suggest to us some bounds on what the probability can be. The probability must be less than the expected value. Given how unlikely a particular week getting at least one of each day present, two particular weeks both getting every day present can be estimated (again, not exactly calculated) as $\approx 0.0072^2$ which when applying inclusion exclusion correctly would have accounted for in the next step subtracting approximately $\approx\binom{52}{2}.0072^2\approx .07$. Each subsequent step in inclusion-exclusion should have gotten us closer and closer to the final answer.

So, as a very dirty estimation, the probability should be somewhere between $0.3$ and $0.37$ for at least one week to have at least one birthday per day.

Some python code for a simulation:

import random
import numpy as np

count=0
for i in np.arange(10000):
   birthdays = []
   for x in np.arange(250):
      birthdays.append(random.randint(1,364))
   overallflag = 0
   for x in np.arange(52):
      weekflag = True
      for y in np.arange(7):
         if 7*x+y+1 not in birthdays:
            weekflag = False
            break
      if weekflag == True:
         overallflag = 1
         break
   count += overallflag
print(count)

When running for 100000 iterations, I got an estimated probability of $0.31988$

Related Question