Problem 4 (20 points). Let us nish the calculation about variance left in lecture 1. Consider the simple hash scheme. for a perfectly random hash h we throw ball 1 ..... 71 into h(1) ..... Mn) directly. Fix a load k: and consider the indicator variable Z that denotes whether bin 2 has 16 balls or not. 1. Prove that 'Covar(Zi, Zj)' = 0(1) for any constant k. 2. Show that Var(Zl + . . . + Zn) = C(11). 3. Apply the Chebyshev's inequality to conclude that with prob 1 nil/2, the number of bins with exact k: balls is m i 001\"\")