1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If you only want to use the first moment you can use Markov’s inequality. $\endgroup$ – lcv Oct 11 '18 at 7:53
  • $\begingroup$ @lcv Unfortunately, Markov gives a bound on not getting to many collisions, but lower bounding the probability of obtaining at least $L$ collisions seems not possible. Markov $\Pr[X\geq \alpha\cdot\mathbb{E}[X]]\leq\frac{1}{\alpha}$. For $\alpha\leq1$ the bound collapses to something trivial. Which is quite intutive, cause theoretically, it could be possible, that in most iterations far less than $L$ collisions appear and there are some where all pairs form a collision. Of course, this won't happen for the special case here, but this remains to be shown. $\endgroup$ – Memphisd Oct 11 '18 at 8:35
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ would be great, if you could give a reference, but also like this it's a great help, thanks! $\endgroup$ – Memphisd Oct 12 '18 at 7:40
  • $\begingroup$ If I have not misunderstood, Claim 2 of $Var(X) = {m \choose 2}\left(\frac{1}{N} - \frac{1}{N^2}\right)$ gives the same variance as you would get with collisions being independent as in a $Bin\left({m \choose 2}, \frac1N\right)$ distribution - which seems correct though unexpected $\endgroup$ – Henry Oct 13 '18 at 10:25
  • 2
    $\begingroup$ @Henry nice observation. I think we can pull off the following ridiculously simpler proof. The variance of the sum of bernoullis is the sum of all covariances. The diagonals sum to the variance of the binomial, and we'll show all off-diagonal covariances are zero. If $\{i,j\} \cap \{k,l\} = \emptyset$ then $I_{i,j}$ and $I_{k,l}$ are independent. The remaining case is $|\{i,j\} \cap \{k,l\}| = 1$, then the covariance is Pr[three samples collide] - Pr[two samples collide]Pr[two samples collide] = $1/N^2 - 1/N^2 = 0$ QED. $\endgroup$ – usul Oct 13 '18 at 14:56
  • 1
    $\begingroup$ @usul, i just noticed that comment of Henry, isn't this cause the indicator variables are pairwise independent, and therefore the variance is just the sum of the variances of the $I_{i,j}$? $\endgroup$ – Memphisd Oct 15 '18 at 10:44
1
$\begingroup$

$\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$.

$\endgroup$
  • $\begingroup$ @usul : Thank you for your comment. This mistake is now corrected. $\endgroup$ – Iosif Pinelis Oct 14 '18 at 2:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.