Probability that a random hash from a universal family is injective
By definition, a family of hash functions $H$ with range of size $m$ is universal if for all $x \neq y$ in the domain of $H$,
$$
\Pr_{h \sim H} [h(x) = h(y)] \leq \frac{1}{m}.
$$
In your case, $m = N^2$. Let the $N$ elements in $S$ be $x_1,\ldots,x_N$. Using the union bound,
$$
\Pr_{h \sim H} [h(x_1),\ldots,h(x_N) \text{ not all distinct}] \leq
\sum_{1 \leq i &lt; j \leq N} \Pr_{h \sim H}[h(x_i) = h(x_j)] \leq \frac{\binom{N}{2}}{N^2} \leq \frac{1}{2}.
$$
In other words, a random $h$ is successful with probability at least $1/2$. Therefore the expected number of times until a successful $h$ is chosen is at most $2$.