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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.