I am going through some old exams in one of my courses, and I don't have access to solutions. I've found a problem which I am not sure how to tackle. I am not looking for the answer but some help/guidance if possible.

Consider a class of hash functions , $\mathcal{H}$, over a finite universe ${U}$ into $\{0, ... , n-1\}$. Where $|U| > 1$ and $n > 1$.

Show that for any family of hash functions $\mathcal{H}$ the following holds: $$ Pr[h(u_1) = h(u_2)] \geq \frac{1}{n} - \frac{1}{|U|} $$ Here, the probability is over the choice of the hash function $h$ drawn uniformly at random from the family $\mathcal{H}$.

  • $\begingroup$ Is the required "$\forall u_1, u_2$" after the $Pr_{h \in \mathcal{H}}[$ or before it? $\endgroup$ – jbapple Dec 15 '19 at 20:21
  • $\begingroup$ No, it is not required for all $u_1$ and $u_2$, but for two choosen "worst ones". $\endgroup$ – Nathanson Dec 16 '19 at 20:33
  • $\begingroup$ Let me restate: for the formula to be valid, $u_1$ and $u_2$ must be bound. Is that binder "$\exists$" or is it "$\forall$"? Where does it appear in the formula? $\endgroup$ – jbapple Dec 17 '19 at 1:14
  • $\begingroup$ Can you edit the question to specify what $u_1$ and $u_2$ are (or how they are chosen). $\endgroup$ – narek Bojikian Jan 27 '20 at 12:37

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.