Probability that a random hash from a universal family is injective

Question

This is a homework question, I don't want an actual answer, but rather guidance on how to obtain the correct answer. The question is as follows:

In class we saw universal hashing as the solution to processing N elements in the range {0,1,...u-1}, arriving one at a time. Using universal hashing we can get O(1) processing time for each request, but in expectation. Hence sometimes we might get unlucky and processing time might be longer. Consider another scenario where we are given the N requests in advance. Can we process them together and store in a hash table so that any future lookup request for any of these items can be processed in worst case O(1) time (so no uncertainty or expectation here)? In this problem you will design a solution for this, again using universal hashing.

You are given a set S of N items in the range {0,1,...u-1) in advance. Consider the following algorithm that stores these items into a table of size N*N.

SquareHash(S, u)
Input: A set S of N items, an integer u such that
each item is in {0,1, ... , u-1}
Output: A hash table of size N*N and a corresponding hash function
1. Initialize a table T of size N*N
2. While true
        3. Pick a function h uniformly at random from a universal family H
        that maps {0,1, ... , u-1} to {0,1, ... , N*N-1}
        // Assume that this can be done in O(1) time
        4. Insert all the elements of S into T using h as the hash function
        5. If T has no collisions, return (T,h). Otherwise empty T

Clearly if the above algorithm terminates then it will produce a table with no collisions and hence any future lookup will be in O(1) time guaranteed. However in the worst case the algorithm might run forever. Show that this is unlikely. In particular, compute the expected running time of the algorithm above. [Hint: Each time a function h is picked, compute the probability (or a lower bound on it) that the resulting table will have no collisions. Then use the fact that if a coin of bias p is flipped until it turns up Heads, the expected number of flips is 1/p]

I understand intuitively this is unlikely to run forever. If a hash function causes a collision, it will pick another one until it finds one that does not cause any collisions. However, I am unsure of how exactly to prove this formally and how to compute the expected running time. I know that the probability of two elements colliding is 1/m, where m is the expected range of outputs.

Answer 1

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