1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ do you want a week, or a stretch of 7 days $\endgroup$ – Saketh Malyala Dec 5 '19 at 12:49
  • 1
    $\begingroup$ I prefer a week from Monday to Sunday :-) $\endgroup$ – Mundron Dec 5 '19 at 12:52
  • $\begingroup$ Be very careful with using stars-and-bars in probability questions. It is usually the case that scenarios that you counted using stars-and-bars are not equally likely to occur. Consider for instance the case of flipping two coins and counting the number of heads. There are three outcomes, $0$ heads, $1$ head, or $2$ heads. Yet despite this, the probability of having gotten $1$ head out of two flips is $\frac{1}{2}$, not $\frac{1}{3}$. Remember $Pr(A)=\frac{|A|}{|S|}$ only works when talking about equiprobable sample spaces. You win or lose a lottery, but probability of winning isn't 1/2 $\endgroup$ – JMoravitz Dec 5 '19 at 13:11
  • $\begingroup$ As for actually calculating this, it seems far too tedious and case focused to have a legible answer. I would be satisfied with a computer driven simulation. If you insist on a pen-paper solution, consider using generating functions and calculating the opposite probability, where no week had all seven days used. $\endgroup$ – JMoravitz Dec 5 '19 at 13:16
  • $\begingroup$ I see that I have to be careful and I understand your argument. But can you point out where I made this mistake? $\endgroup$ – Mundron Dec 5 '19 at 14:01
1
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot! I need a bit to fully understand our answer, but this is exactly what I was looking for. My simulation states around $\approx 0.317$. :-) $\endgroup$ – Mundron Dec 5 '19 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.