Are those definitions of universal hash family equivalent? I've seen two definitions of a universal hash family, and my questions is if those are equivalent, i think they are and will explain why but i'm not sure if it is.

Definition 1:

$H$ is a universal hash family if and only if $$\mathbb{Pr_{h \in H}}[h(k) = h(l)] = 1/m$$

where $k \neq l$ and $k,l\in Key$ and $m$ is the Size of the Hashtable

Definition 2:

The same as above just substitute the equals sign with a less or equal sign.

Well, i think those definitions are equivalent, because i think the probability for a collision can't possibly be strictly less than 1/m or am i missing something?

P.S.
I'm assuming that the cardinality of Key is bigger than the size of the hashtable m
I'm assuming that the cardinality of Key is bigger than the size of the hashtable m


There are still families with collision probability less than $1/m$, e.g., with three keys and two buckets,

$$\{(2, 1, 1), (1, 2, 1), (1, 1, 2)\}$$

has collision probability $1/3 &lt; 1/2$, and there are other counterexamples for all other parameter settings. The most plausible path to your intuition being true would be if $h(k)$ and $h(l)$ were necessarily independent, but they're not and can in fact be anti-correlated.