# Probability of colisson for classes of hash functions

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}$$.

• Is the required "$\forall u_1, u_2$" after the $Pr_{h \in \mathcal{H}}[$ or before it? – jbapple Dec 15 '19 at 20:21
• No, it is not required for all $u_1$ and $u_2$, but for two choosen "worst ones". – Nathanson Dec 16 '19 at 20:33
• 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? – jbapple Dec 17 '19 at 1:14
• Can you edit the question to specify what $u_1$ and $u_2$ are (or how they are chosen). – narek Bojikian Jan 27 '20 at 12:37