Problem 2 (20 points.). Consider a random distribution D over those bins [n] = {1, 2, ..., n}. We define its collision probability to be Pr [a = b] a~D, b~D where a and b are drawn from D independently. Prove that the uniform distribution has the smallest collision probability among all dis- tributions. This is the reason why we only consider uniform distribution over n bins in hash functions. Hint 1. Define a random variable X (depends on D) such that the collision probability is equal to E[X2] then use Var(Y) 2 0 = E(Y2) - E? (Y) 20 = {E(Y2) } 1/2 > E(Y ) Now put Y = [X - E(X) | we get {EX-E(X) |?}1/2 > E X-E(X) | = [E{X-E(X) }21/2 > EX-E(X)| = \\Var(X) 2 EX - E(X)|