[Math] Probability of Multiple Collisions in the Birthday Problem

birthdayprobability

I need help with an approximation concerning the birthday problem. In a recent MAA Monthly (August-September 2013) article "Simple Approximation Formulas for the Birthday Problem" by Matthias Arnold and Werner Glass, the authors claim the probability $p$ that out of $n$ people at least $k$ birthdays occur on a single day in a year with $c$ days is approximately
$$p\approx1-\exp\,\left(\!n^k{\textrm{e}}^{-n/c}\left(\!\frac n{c(k+1)} -1\!\right)^{\!-1}c^{1-k}(k!)^{-1}\!\right).$$

The authors cite this formula from a 1989 paper "Methods for Studying Coincidences" by Persi Diaconis and Frederick Mosteller. Unfortunately, this reference only claims the formula comes from unpublished work and provides no further references. Can anyone provide insight about how to obtain such a formula?

Best Answer

Here is a possible approach which seems to gets most of the way to that expression:

Let $F_\lambda(x)=P(X\le x)$ be the cumulative distribution function for a Poisson distribution with mean $\lambda$. We will have $F_\lambda(x-1) \lt 1 - P(X=x)=1-e^{-\lambda} \frac{\lambda^x}{x!}$ but this will be close for $x \gg \lambda$.

Then for an individual day, the probability of fewer than $k$ birthdays falling on that day has a binomial expression but can be approximated with a Poisson expression using $\lambda=\frac{n}{c}$. So we might say it could be about $1-e^{-n/c} \dfrac{(n/c)^k}{k!}$.

Making the slightly wrong assumption that the number of birthdays falling on each day is almost independent of the number on other days, the probability they are all below $k$ might be about $\left(1-e^{-n/c} \dfrac{(n/c)^k}{k!}\right)^c$ which, using $\left(1-\frac{b}{m}\right)^m \approx \exp(-b)$, might be about $\exp\left(-e^{-n/c}\dfrac{n^k}{c^{k-1} k!} \right)$. Subtract this from $1$ to get an approximation to the probability that out of $n$ people at least $k$ birthdays occur on a single day in a year with $c$ days.

This not quite the same expression as you quoted, as it has $-1$ where your quote has $\left(\dfrac n{c(k+1)} -1\right)^{-1}$, but it has all the other elements.

Related Question