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.

  • $\begingroup$ 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$? $\endgroup$ – usul Mar 1 '17 at 16:42
  • $\begingroup$ Not that I know... $\endgroup$ – Clement C. Mar 1 '17 at 16:45
  • 2
    $\begingroup$ 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. $\endgroup$ – Sungjin Kim Mar 5 '17 at 2:09
  • 1
    $\begingroup$ @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. $\endgroup$ – esg Mar 5 '17 at 19:17
  • $\begingroup$ @i707107 Indeed, that's quite useful. Thanks for the link! $\endgroup$ – 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.)

  • $\begingroup$ 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$)? $\endgroup$ – Clement C. Mar 4 '17 at 20:28
  • $\begingroup$ Yes, it is with regard to $n$. $\endgroup$ – esg Mar 4 '17 at 21:23
  • $\begingroup$ 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). $\endgroup$ – 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.)


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.