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.



Birthday problem with unequal probability: expected number of draws before the $m$-th collision?
(1) Simple bounds: 


For $m=1$ (see [here](https://mathoverflow.net/questions/257027)
(or [here](http://eprint.iacr.org/2005/318) and [here](https://arxiv.org/abs/1402.5547))) 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.)


