Let $D$ be a distribution with collisionentropy $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?
Asked
Viewed
544 times

3$\begingroup$ This is now answered in mathoverflow.net/a/257340/101775 $\endgroup$ – Dominique Unruh Dec 16 '16 at 10:52

1$\begingroup$ Possible duplicate of Birthday inequality for nonuniform distributions for fixed collision probability (random allocation, collision probability) $\endgroup$ – usul Jun 26 '18 at 12:08