Timeline for lower bound the probability of at least L collisions
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 15, 2018 at 10:44 | comment | added | Memphisd | @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}$? | |
| Oct 13, 2018 at 14:56 | comment | added | usul | @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. | |
| Oct 13, 2018 at 10:25 | comment | added | Henry | 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 | |
| Oct 12, 2018 at 7:40 | vote | accept | Memphisd | ||
| Oct 12, 2018 at 7:40 | comment | added | Memphisd | would be great, if you could give a reference, but also like this it's a great help, thanks! | |
| Oct 11, 2018 at 20:39 | history | edited | usul | CC BY-SA 4.0 |
show a step
|
| Oct 11, 2018 at 20:31 | history | answered | usul | CC BY-SA 4.0 |