2-universal hash functions, which have collision probability 1/n for any two items. A k-universal hash function h : U [n] is any random hash function that satisfies, for any inputs x1, . . . , xk U, Pr[h(x1) = h(x2) = . . . = h(xk)] 1 nk1 .

1. (2 points) Suppose you hash n balls into n hash buckets using a 2-universal hash function. Show that for t = 5n, the number of pairwise collisions exceeds t with probability at most 1/10.

2. (2 points) Use the above to argue that for t = 4 n, that the maximum load on any bin exceeds t with probability at most 1/10. Hint: Dont use a union bound.

3. (2 points) Generalize this result to k-universal hash functions for k > 2. Show that if t = cn1/k for large enough constant c, that the probability of the maximum load exceeding t at most 1/10. Hint: Instead of pairwise collisions, consider the expected number of k-wise collisions.