lower bound the probability of at least L collisions

Question

Lets say we get a list $M$ containing $|M|=\sqrt{L\cdot N}$ randomly and independtly drawn elements from a set of size $N$. And lets denote the $i$-th element of the list $M$ by $M[i]$.

If we now ask for the amount of collisions $X$ in $M$, where a collision is defined as a pair of indices $(i,j)$, $i\neq j$ with $M[i]=M[j]$ we obviously have $\mathbb{E}[X]=\frac{\binom{|M|}{2}}{N}=\frac{\binom{\sqrt{LN}}{2}}{N}\approx L$.

But unfortunately this is just the expected value and gives no information about the probability distribution. Is there anything we can say about the probability of $X$ deviating from its expectation here?

We could define indicator variables $X_{i,j}$ with $X_{i,j}= 1 \Leftrightarrow M[i]=M[j]$. Because the elements of M are drawn independently at random it holds that $X_{i,j}\sim \textrm{Ber}_\frac{1}{N}$. Unfortunately these indicator variables are not independent, otherwise the number of collisions would be binomial distributed and we could use a Chernoff like argument. Another approach to bound the probability that $X\geq \alpha\mathbb{E}[X]$ for some $\alpha<1$ could therefore be to somehow bound the variance of the sum of indicator variables and use the Chebyshev inequality. So far I did not find a non-trivial way to bound this variance.

This problem looks so common, that I can not imagine, that it hasn't been studied exhaustively in literature. Unfortunately, I was not able to find a solution somewhere so far. Help in form of own calculations as well as literature suggestions would be appreciated

Answer 1

Main claim. $$\Pr[|X - \mathbb{E} X| \geq t] \leq \frac{\mathbb{E} X}{t^2} \approx \frac{L}{t^2}. $$ You can bound the variance and use Chebyshev's Inequality as you suggest, and the calculations are not pretty but it helps if someone has already done them. Here's a sketch. Let's write $m = |M|$ for the number of samples, and $N$ for the size of the set. Let $I_{i,j}$ equal $1$ if $M[i]=M[j]$ and zero otherwise, then $X = \sum_{i < j} I_{i,j}$, the number of collisions.

Let $A_x$ be the probability of drawing element $x$ from the set. I understand you are interested in the uniform case $A_x = \frac{1}{N}$ but I only know how to solve the general case.

Claim 1 (as you wrote). $\mathbb{E} X = {m \choose 2} \|A\|_2^2$. Proof: the probability that $M[i] = M[j]$ is $\sum_x A_x^2 = \|A\|_2^2$, then use linearity of expectation. For the uniform distribution, $\|A\|_2^2 = \frac{1}{N}$.

Claim 2. (I will sketch below.) $$ Var(X) = {m \choose 2}\left(\|A\|_2^2 - \|A\|_2^4\right) + 6 {m \choose 3} \left(\|A\|_3^3 - \|A\|_2^4\right) .$$ For the uniform distribution, $\|A\|_3^3 = \frac{1}{N^2}$, so the second term cancels and we get: $$ Var(X) = {m \choose 2}\left(\frac{1}{N} - \frac{1}{N^2}\right) \leq \mathbb{E} X . $$

Corollary 3. Now we can use Chebyshev's inequality, i.e. $$ \Pr[ |X - \mathbb{E} X| \geq t] \leq \frac{Var(X)}{t^2} \leq \frac{\mathbb{E} X}{t^2} . $$

---

The only thing for me to convince you of is Claim 2, which comes from a counting argument. Remember $I_{i,j}$ is the indicator for a collision between $i$ and $j$th samples.

\begin{align} Var(X) &= Var\left(\sum_{i<j} I_{i,j}\right) \\ &= \mathbb{E} \left(\sum_{i<j} (I_{i,j} - \mathbb{E}I_{i,j})\right)^2 \\ &= \sum_{i<j} \sum_{k<\ell} \mathbb{E} \left(I_{i,j} - \mathbb{E}I_{i,j}\right)\left(I_{k,\ell} - \mathbb{E}I_{k,\ell}\right) \\ &= \left(\sum_{i<j} \sum_{k<\ell} \mathbb{E} I_{i,j} I_{k,\ell} \right) - 2 \left(\sum_{i<j} \sum_{k<\ell} \mathbb{E} I_{i,j} \mathbb{E} I_{k,\ell} \right) + \left(\sum_{i<j} \sum_{k<\ell} \mathbb{E} I_{i,j} \mathbb{E} I_{k,\ell} \right) \\ &= \sum_{i<j} \sum_{k<\ell} \mathbb{E} I_{i,j} I_{k,\ell} - \mathbb{E} I_{i,j} \mathbb{E} I_{k,\ell} . \end{align} (Note $\mathbb{E} I_{i,j} \mathbb{E} I_{k,l} = \|A\|_2^4$.) Now for each $i,j,k,\ell$ in this sum, we have three cases:

• If $i=k, j=\ell$ then $I_{i,j} = I_{k,\ell}$ and $\mathbb{E} I_{i,j}I_{k,\ell} = \mathbb{E}I_{i,j} = \|A\|_2^2$. There are ${m \choose 2}$ such terms.

• If $\left| \{i,j\} \cap \{k,\ell\} \right| = 1$, then we can calculate $\mathbb{E} I_{i,j}I_{k,\ell}$ is the probability that three independent samples are all the same element, which is $\sum_x A_x^3 = \|A\|_3^3$. We can count to get $6 {m\choose 3}$ such terms, because there are ${m\choose 3}$ triples of distinct indices, and each triple $a<b<c$ appears in the sum $6$ ways, namely $3$ ways to assign $i<j$ to two of $a,b,c$, times $3$ ways to assign $k<\ell$, minus the three combinations where $i=j$ and $k=\ell$.

• If $\{i,j\} \cap \{k,\ell\} = \emptyset$, then the random variables $I_{i,j}$ and $I_{k,\ell}$ are independent and the term is zero. By the way, there are $6{m\choose 4}$ such terms because each choice of $4$ distinct indices $a<b<c<d$ appears six times (count three each with $a=i$ and with $a=k$). Now you can check I've counted all the terms in the sum, since there are ${m\choose 2} {m \choose 2}$ terms and this equals ${m\choose 2}$ (from case 1) plus $6{m\choose 3}$ (from case 2) plus $6{m\choose 4}$ (from case 3).

If this is not complete enough, I can link a reference but I prefer not to self-cite and do not know where else to find this proof (though as you said, it's unlikely to be unique).

Answer 2

$\newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \newcommand{\thh}{\theta} \newcommand{\vpi}{\varphi} \renewcommand{\P}{\operatorname{\mathsf P}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\Var}{\operatorname{\mathsf Var}}$

Let $X_i:=M[i]$ and $n:=|M|$, so that \begin{equation} X=\sum_{1\le i<j\le n}1_{\{X_i=X_j\}}=\binom n2 U,\quad U:=\binom n2^{-1}X=\binom n2^{-1}\sum_{1\le i<j\le n}h(X_i,X_j), \end{equation} $h(x_1,x_2):=1_{\{x_1=x_2\}}$, so that $U$ is a $U$-statistic with kernel $h$ of order $m=2=\;$the number of arguments of $h$.

We have \begin{equation} \E X=\sum_{1\le i<j\le n}\P(X_i=X_j)=\binom n2\frac1N, \end{equation} and \begin{equation} \E X^2=\sum_{\{i,j\}\in\binom{[n]}2}\;\sum_{\{k,\ell\}\in\binom{[n]}2}\P(X_i=X_j,X_k=X_\ell)=\Si_1+\dots+\Si_4, \end{equation} \begin{equation} \Si_1:=\sum_{\{i,j\}\cap\{k,\ell\}=\emptyset}\P(X_i=X_j,X_k=X_\ell)=\frac1{N^2}\,\binom n2\binom{n-2}2, \end{equation} \begin{equation} \Si_2:=\sum_{\{i,j\}\cap\{k,\ell\}=\{i\wedge j\}}\P(X_i=X_j=X_k)=\frac1{N^2}\,\binom n2\binom{n-2}1, \end{equation} \begin{equation} \Si_3:=\sum_{\{i,j\}\cap\{k,\ell\}=\{i\vee j\}}\P(X_i=X_j=X_k)=\frac1{N^2}\,\binom n2\binom{n-2}1, \end{equation} \begin{equation} \Si_4:=\sum_{\{i,j\}=\{k,\ell\}}\P(X_i=X_j)=\frac1{N}\,\binom n2, \end{equation} whence \begin{equation} \Var X=\E X^2-\E^2X=\frac{N-1}{N^2}\,\binom n2. \end{equation}

Now one can use the Paley--Zygmund inequality: for $\thh\in[0,1)$, \begin{multline} \P(X>\thh\E X)\ge 1-\frac{\Var X}{\Var X+(1-\thh)^2\E^2X} \\ = 1-(N-1)\bigg/\bigg[N-1+(1-\thh)^2\binom n2\bigg]\to1 \end{multline} as $n\to\infty$.

The $U$-statistic $U=\binom n2^{-1}X$ is degenerate, since $\Var\E(h(X_1,X_2)|X_1)=\Var\frac1N=0$. Using an appropriate limit theorem for such statistics (see e.g. Theorem 4), we see that $\frac2{n-1}(X-\E X)=n(U-\E U)$ converges in distribution (as $n\to\infty$) to the random variable (r.v.) \begin{equation} \sum_1^N\la_i(Z_j^2-1)=(2/N-1)(Z_1^2-1)+(2/N)\sum_2^N(Z_j^2-1), \end{equation} where the $Z_j$'s are iid standard normal r.v.'s and the $\la_j$ are the eigenvalues of the centered kernel $h(x_1,x_2)-\E h(X_1,X_2)=1_{\{x_1=x_2\}}-\P(X_1=X_2)=1_{\{x_1=x_2\}}-1/N$, so that $\la_1=2/N-1$ (with a corresponding eigenfunction $\vpi_1(x)\equiv1$) and $\la_2=\dots=\la_N=2/N$ with $n-1$ linearly independent eigenfunctions $\vpi_2,\dots,\vpi_N$ satisfying the condition $\sum_{x=1}^N\vpi_j(x)=0$ for $j=2,\dots,N$.