# An extension of the birthday problem

Th birthday problem (or paradox) has been done in many way, with around a dozen thread only on math.stackexchange. The way it is expressed is usually the following:

"Let us take $n$ people "independently" (no twins, etc.). What is the probability that no two people share the same birthday?"

It is abstracted in the following way:

"Let $X_1$, $\cdots$, $X_n$ be $n$ i.i.d. random variables taken uniformly in $[[1, 365]]$. What is the probability that all the $X_i$'s are distinct?"

There are many generalizations, for instance:

"Let $n$, $d$ be two positive integers, $n \leq d$. Let $X_1$, $\cdots$, $X_n$ be $n$ i.i.d. random variables taken uniformly in $[[1, d]]$. What is the probability $p(n,d)$ that all the $X_i$'s are distinct?"

One can show that in the regimen $1 \ll n \ll d$, the probability $p(n,d)$ is logarithmically equivalent to something like $e^{-\frac{n^2}{2d}}$ (Wikipedia) or $e^{-\frac{n^2}{d}}$ (my computations)*. This problem can be reduced to simple combinatorics, and Stirling's formula (for instance) gives the solution.

However, in the real world, the birthdays are not distributed that way. One might also want to estimate the probability that two peoples are born the same half-day, the same hour, etc. The following generalization seems natural:

"Let $\mu$ be a probability measure on $[0,1]$ absolutely continuous with respect to the Lebesgue measure. Let $n$, $d$ be two positive integers. For $k \in [[0,d-1]]$, let $a_k := [k/d, (k+1)/d]$. Let $X_1$, $\cdots$, $X_n$ be $n$ i.i.d. random variables in $[0,1]$ with distribution $\mu$. What is the probability $p(n,d)$ that all the $X_i$'s lie in different elements of the partition?"

I would expect the solution to be something like $e^{-C(\mu) \frac{n^2}{d}}$, with perhaps some explicit expression of $C(\mu)$. But the combinatorial solutions do not work as well in this setting, and all I can get are very crude bounds when the density of $\mu$ is bounded. In addition, I would expect $C(\mu)$ to be minimal when $\mu$ is the Lebesgue measure, but I don't know how to prove it. One might wonder what happens when $\mu$ is no longer absolutely continuous, but this might be a bit too broad of a generalization.

I am sure this problem has been done to death, but I don't have any access to the literature right now, and quick search didn't yield anything (the generalizations of the birthday problem I found are quite different). Any result/proof/reference related to the problems above would be nice.

.* By the way, any rigorous proof of either of the two facts (or of any similar-sounding result) is appreciated. I don't know which I can trust more, between my computations and Wikipedia.

• Reference tackling the same problem. – nikhil_vyas Jul 7 '16 at 12:30

Let's rephrase the problem:

There are $m$ bins, and $n$ items placed independently into a random bin with probability $p_k$ of going into bin $k\in\{1,\ldots,m\}$. What is the likelihood that no to items go into the same bin?

Let's start with an approximate solution which is good for giving some intuition about the problem and works well as long as $n\ll m$.

For any to items, the probability of them going into the same bin is $q=\sum_{k=1}^m p_k^2$. Hence, the probability that they do not go into the same bin is $1-q$. Since there are $n(n-1)/2$ different pairs of item, if we make the approximation that any two pairs of items are independent (true if pairs have no items in common and almost true if the two pairs have one item in common), we find the likelihood that no pair go into the same bin to be $\approx(1-q)^{n(n-1)/2}\approx e^{qn(n-1)/2}$.

Now, let's do this a bit more formally. If we define the polynomial $$F(x)=\prod_{k=1}^m (1+p_kx)=\sum_{j=0}^m \frac{f_j x^j}{j!},$$ the coefficient $f_n$ is the likelihood that that $n$ items go into $n$ distinct bins: sums over all different ways to pick $n$ bins and the likelihood that the $n$ items be placed into these bins in any order (the factor $n!$).

We can now make an approximation: $$\begin{split} F(x) =&\prod_{k=1}^m (1+p_kx) = \exp\left\{\sum_{j=1}^m\ln(1+p_jx)\right\}\\ =&\exp\left\{\sum_{j=1}^m p_jx-\frac{p_j^2x^2}{2}+\frac{p_j^3x^3}{3}-\cdots\right\}\\ =&\exp\left\{x-\frac{q_2x^2}{2}+\frac{q_3x^3}{3}-\cdots\right\}\\ =&e^x\cdot e^{-q_2x^2/2}\cdot e^{q_3x^3/3}\cdot e^{-q_4x^4/4}\cdots\\ \end{split}$$ where $q_r=\sum_{k=1}^m p_k^r$ (so the above $q=q_2$ while $q_1=1$). We can show that $q_k\le q_2^{k-1}$ (e.g. from $q_r^2\ge q_{r-1}q_{r+1}$) which tells us $q_2$ is the dominant adjustment.

If we make the expansion $$\begin{split} \exp\left\{-\frac{q_2x^2}{2}+\frac{q_3x^3}{3}-\cdots\right\} =&\sum_{k=0}^\infty\frac{1}{k!} \left(-\frac{q_2x^2}{2}+\frac{q_3x^3}{3}-\cdots\right)^k\\ =&1-a_2x^2+a_3x^3-a_4x^3+\cdots\\ \end{split}$$ we get $a_2=q_2/2$, $a_3=q_3/3$, $a_4=q_4/4-q_2^2/8$, etc. Entering these into the power expansion for $F(x)$, we get $$\begin{split} F(x)=&e^x\cdot\left(1-a_2x^2+a_3x^3-a_4x^3+\cdots\right)\\ =&\sum_{n=0}^\infty\left(\frac{1}{n!} -\frac{a_2}{(n-2)!}-\frac{a_3}{(n-3)!}-\cdots\right)\cdot x^n\\ =&\sum_{n=1}^\infty\big(1-a_2n(n-1)+a_3n(n-1)(n-2)-\cdots\big)\cdot\frac{x^n}{n!}\\ \end{split}$$ so the effect of $a_rx^r$ is an adjustment $a_rn(n-1)\cdots(n-r+1)$ which for $r\ll n$ has the same magnitude as $a_rn^2$.

If we ignore $q_r$ for $r>2$ and take the effect of $a_{2r}x^{2r}$ to be $\approx a_{2r}[n(n-1)]^r$ (which is true for $r=1$ but only approximate for $r>1$, we get the original approximation: $e^{-q_2n(n-1)/2}$.

I have no idea for your main question, but I know how you got, for the uniform distribution case, a formula distinct from that of Wikipedia -- because I did the same mistake earlier today.

You select $n$ values out of a space of size $d$, each selection being uniformly random. We assume that $n \ll d$ (but not necessarily that $n^2 \ll d$, which is the crucial point). The probability of there being no collision is:

$$p(n,d) = \frac{d!}{d^n(d-n)!}$$

(there are $\frac{d!}{(d-n)!}$ possible selections with no collisions, out of $d^n$ if we allow collisions).

Using Stirling's formula ($k! \approx \sqrt{2\pi k}(\frac{k}{e})^k)$, we get:

$$p(n, d) \approx d^{-n} \sqrt{\frac{d}{d-n}} \left(\frac{d}{e}\right)^d\left(\frac{d-n}{e}\right)^{n-d}$$

Since $n \ll d$, the part with the square root is very close to $1$, so we ignore it. The expression then becomes:

$$p(n, d) \approx e^{-n} \left(1-\frac{n}{d}\right)^{n-d} = e^{-n + (n-d)\ln (1-\frac{n}{d})}$$

No we replace the log with its Taylor approximation, and, that's the tricky point, you have to use degree 2. This means that:

\begin{eqnarray} -n + (n-d)\ln (1-\frac{n}{d}) &=& -n + (n-d)\left(-\frac{n}{d} - \frac{n^2}{2d^2} + O\left(\frac{n^3}{d^3}\right)\right) \\ &=& -\frac{n^2}{d} - \frac{n^3}{2d^2} + \frac{n^2}{2d} + O\left(\frac{n^3}{d^2}\right) \\ &=& -\frac{n^2}{2d} + O\left(\frac{n^3}{d^2}\right) \end{eqnarray}

Hence the result:

$$p(n,d) \approx e^{-\frac{n^2}{2d}}$$

which is the formula given in the Wikipedia page on the birthday "paradox". In the expression above, when we replace the log with its approximation, the degree 1 terms cancel out, which is why we have to go to degree 2. Stopping at degree 1 was my mistake and, I presume, yours too.