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



lower bound the probability of at least L collisions
**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).


