4
$\begingroup$

I have another variation of a birthday problem to solve. Given $n$ people and $m$ birthdays (let's keep in generic...), what would be the probability that none of the people has a unique birthday date? I've already run out of ways to approach the problem...

$\endgroup$
1
  • $\begingroup$ As a further variant, the expected number of days with exactly one person having that birthday is $n\left(1-\frac1m\right)^{n-1}$ $\endgroup$
    – Henry
    Nov 24 '17 at 10:45
5
$\begingroup$

The Inclusion-Exclusion principle gives a formula of sorts. Start with a basic $m^n$ possible sets of birthdays.
We want to subtract the number of ways Person1 has a unique birthday. He has one of $m$ birthdays, and everyone else must fit into $m-1$ days. That is $m(m-1)^{n-1}$ ways. In fact, subtract that $n$ times, because there are $n$ people who might have a unique birthday.
But if two people have unique birthdays. There are $m\choose2$ ways to choose the days and $n\choose2$ ways to choose the people. They match up in $2!$ ways. We subtracted that twice (once for A and once for B) and need to add it back in once.
If three people have unique birthdays, we have already subtracted three times (for A,B,C), added back in three times (for AB,AC,BC) and need to subtract off again.
In the end, it comes to $$\frac{m^n-mn(m-1)^{n-1}+2!{m\choose2}{n\choose2}(m-2)^{n-2}-3!{m\choose3}{n\choose3}(m-3)^{n-3}+...}{m^n}$$ EDIT: Here is an approximation for large $n$ and $m$.
The number of people with a given birthday is a Poisson variable with parameter $\lambda=n/m$, so the probability it is not $1$ is $1-\lambda e^{-\lambda}$. So the chance that no birthday is unique is $$\left(1-\frac nme^{-n/m}\right)^m$$ This goes from $0$ to $1$ when $ne^{-n/m}\approx1$, or $m\approx n/\ln n$

$\endgroup$
5
  • $\begingroup$ The logic seems fine, but a short simulation or a toy example show that it is incorrect... $m=n=2$ comes up to 0.25, but in fact the probability that both collide is 0.5 $\endgroup$
    – kck
    Oct 15 '15 at 15:12
  • $\begingroup$ Now it works! Thank you! $\endgroup$
    – kck
    Oct 15 '15 at 15:15
  • $\begingroup$ Ah. Firstly, the question of $0^0$. If you have no more people to fit into no more days, that should not affect the calculation, so I say $0^0=1$. But the other thing is that, having chosen the 2 people and 2 days, there is $2!$ ways to fill them. $\endgroup$
    – Empy2
    Oct 15 '15 at 15:18
  • $\begingroup$ Thanks, Michael. A follow up question: what do you mean by "They match up in 2! ways."? $\endgroup$
    – kck
    Oct 18 '15 at 16:42
  • $\begingroup$ If the people are $A$ and $B$, and the birthdays are $1st$ and $3rd$, then either $A$'s is the first and $B$'s the third, or vice versa. $\endgroup$
    – Empy2
    Oct 18 '15 at 18:20

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.