X = {x1,...,xk} is a set of input values, Y = {0, 1, . . . , m 1} is a set of hash values, and H is an [X Y ]-valued random variable.

We know that for any hash value y Y , the expected number of input values that hash to y is k/m, where k = |X| and m = |Y|. However, in determining the time it takes to look up a particular input value (say x1), we need to know how many input values xi hash to the same value as x1 does.

(a) Let N be the number of input values (besides x1) that hash to the same value as x1. Show that if H is a nice random hash function, that E(N) = (k 1)/m.

(b) Show that this is not necessarily true if H satisfies the first property but not the second. That is, give an example H where Y1 and Yi are not independent, and show that E(N) = (k 1)/m. Hint: you can make N = k 1 by picking a bad hash function (show how!)