Let $D$ be a distribution with collision-entropy $k$, i.e., $H_2(D) = k$. Let $n$ samples are chosen independently according to the distribution $D$. Let $E_n$ be the event that there is no collision among the $n$ samples. We are interested in a non trivial upper bound for the probability of the event $E_n$. i.e., $Pr[E_n] \le ?$ or how many samples are needed so that the chance of one collision is at least 1/2?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ This is now answered in mathoverflow.net/a/257340/101775 $\endgroup$– Dominique UnruhDec 16, 2016 at 10:52
-
1$\begingroup$ Possible duplicate of Birthday inequality for non-uniform distributions for fixed collision probability (random allocation, collision probability) $\endgroup$– usulJun 26, 2018 at 12:08
Add a comment
|