Problem 2 (20 points). Consider a random distribution D over those bins [n] : {1, 2, . . . ,n}. we dene its collision probability to be Pr [(1 : 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 it bins in hash functions