# Birthday problem with unequal probability: expected number of draws before the $m$-th collision?

Let $p$ be an arbitrary distribution over $\mathbb{N}$, and $m\geq 1$ be an integer. Given an infinite sequence of i.i.d. draws $(X_i)_{i\geq 1}$ from $p$, define a collision as a pair $(i,j)$ with $i<j$ and $X_i=X_j$.

Let $M_m$ be the minimum integer $\ell$ such that $m$ collisions happen in $(X_i)_{1\leq i\leq \ell}$. I am interested in (bounds on) the expectation $\mathbb{E}[M_m]$ (as a function of $m$ and $p$; most likely its $\ell_2$-norm $\lVert p\rVert_2$).

• For $p$ being the uniform distribution over $\{1,\dots,n\}$ and $m\geq 2$, this is the standard birthday paradox, and we have $\mathbb{E}[M_1] \sim_{n\to\infty} \sqrt{\frac{\pi n}{2}}$.

• For $p$ being an arbitrary distribution, the (exact, although not necessarily easy to use) distribution of $M_1$ can be found in (2) of [CP00].

[CP00] also studies the general case of $M_m$ to pinpoint its exact distribution, and its limiting distribution under some assumption on $p$ (where $p$ is seen as a sequence $p=(p_n)_{n\in\mathbb{N}}$ and one lets $n\to\infty$). However, I can't seem to find how to derive simple bounds for $\mathbb{E}[M_m]$ and even $\mathbb{E}[M_1]$ from there. (By simple, I mean as above: while not necessarily tight, closed-form and depending on $m$ and simple functionals of $p$ only such as it's $\ell_r$ norms).

[CP00] Camarri, Michael, and Jim Pitman. "Limit distributions and random trees derived from the birthday problem with unequal probabilities." Electron. J. Probab 5.2 (2000): 1-18.

• Do we have good answers for easier cases, like $\mathbb{E} M_1$ for non-uniform $p$ and $\mathbb{E} M_2$ for uniform $p$? – usul Mar 1 '17 at 16:42
• Not that I know... – Clement C. Mar 1 '17 at 16:45
• Similar question in case $p$ is uniform on $\{1,2,\ldots, n\}$ was raised by me in a comment to math.stackexchange.com/questions/1941394/… and I answered my own question there. – Sungjin Kim Mar 5 '17 at 2:09
• @i707107 Thanks, that's a useful addition. I suspect that the result for the uniform case is much older, but have been unable to spot it. – esg Mar 5 '17 at 19:17
• @i707107 Indeed, that's quite useful. Thanks for the link! – Clement C. Mar 5 '17 at 20:14

(1) Simple bounds:

For $m=1$ (see here (or here and here)) the inequalities

\begin{align*} \sqrt{\frac{\pi}{2}}{1\over \lVert p\rVert_2}&\leq \mathbb{E}(M_1)\leq \sqrt{\frac{\pi}{2}}{1 \over \lVert p\rVert_2}+ {\max_i( p_i)\over \lVert p\rVert_2^2}\mbox{ and }\\ \sqrt{\frac{\pi}{2}}{1\over \lVert p\rVert_2}&\leq \mathbb{E}(M_1)\leq 2 \sqrt{\frac{\pi}{2}}{1 \over \lVert p\rVert_2}\end{align*} hold. Since $M_m$ is obviously stochastically smaller than the sum of $m$ independent copies of $M_1$

$$\sqrt{\frac{\pi}{2}}{1\over \lVert p\rVert_2}+1 \leq \mathbb{E}(M_m)\leq 2m \sqrt{\frac{\pi}{2}}{1 \over \lVert p\rVert_2}$$

(2) Precise asymptotics:

Assume in the sequel the conditions and notation of Thm. 4 in [CP00]. Then $$\lVert p(n)\rVert_2\, M_m(n)=s_nR_{nm}\mbox{ in [CP00]})$$ converges in distribution to a random variable $\eta_m$, where the joint distribution of $(\eta_1,\eta_2,\ldots,\eta_m)$ is given in Thm. 6. It is not hard to see that the random variables $\lVert p(n)\rVert_2\, M_m(n)$ are uniformly integrable. Thus $\eta_m$ is integrable and $$\mathbb{E}\left(\lVert p(n)\rVert_2 M_m(n)\right)\longrightarrow \mathbb{E}(\eta_m)$$ Thus asymptotically $$\mathbb{E}(M_m(n))\sim \frac{C_m}{\lVert p(n)\rVert_2}$$ where $C_m=\mathbb{E}(\eta_m)$. The distribution of $\eta_m$ depends on all the "large cell" parameters $\theta_1,\theta_2,...$ and $C_m$ will in general not be of a convenient explicit form. But the case $\theta_1=0$ is simple. Here we get from Thm. 6 that $\mathbb{P}(\eta_m>x)=\mathbb{P}(\mathrm{Poiss}(\tfrac{1}{2}x^2)\leq m-1)$ and integrating this gives \begin{align*} C_m&={m-\tfrac{1}{2} \choose m-1}\sqrt{{\pi \over 2}} &\mbox{ for } \theta_1=0 \\ %\mbox{ and } C_m&=m+1 &\mbox{ for } \theta_1=1 \end{align*} In particular, for the uniform distribution on $\{1,\ldots,n\}$ $$E(M_2)\sim \tfrac{3}{2}\sqrt{\tfrac{1}{2}\pi n},\; \mathbb{E}(M_3)\sim \tfrac{15}{8} \sqrt{\tfrac{1}{2}\pi n},\ldots\;\;.$$ (This certainly looks "classical", but I haven't found anything in the literature.)

• Thank you! I'll have a deeper look as soon as possible, but that looks like it exactly answers my question. As a side note (to avoid any confusion): the asymptotic equivalents are with regard to $n\to\infty$, right (not $m$)? – Clement C. Mar 4 '17 at 20:28
• Yes, it is with regard to $n$. – esg Mar 4 '17 at 21:23
• So, just for the sake of readers: the conditions of Theorem 4 of [CP00] are that (1) $\lVert p(n)\rVert_\infty\xrightarrow[n\to\infty]{}0$ and (2) $\theta_i\stackrel{\rm def}{=}\lim_{n\to\infty}\frac{p(n)_i}{\lVert p(n)\rVert_2}$ exists for every $i$. (Where $p(n)$ is, wlog, assumed non-increasing). – Clement C. Mar 5 '17 at 20:20

In $l$ trials, the expected number of collisions is $$\dfrac{l(l-1)}{2} \sum_i p_i ^2.$$

A reasonable heuristic (which could likely be made more rigorous with calculations of higher moments) is that $M_m$ is roughly the $l$ for which the above expected value is about $m$. This gives

$$M_m \approx \sqrt{m} / \Vert p \Vert_2$$.

I imagine that this argument could be improved to show $M_m$ is roughly this (within multiplicative constants) almost surely by second-moment method if you like. (Similar to, say, the usual birthday paradox. Or like the independence number of a random graph.)