1 3-wise independent Hashing Le. 'H be a 3-wise independent family of hash functions (H : U > T), |U| = n, |T| = m if and only if the following condition holds. 5} [(h(al) = 061) 0 (M02) = CM2) 0 (M02) = 063)] (1) where a1, a2, 033 are distinct elements in U, 0:1, (12, a3 are 3 elements in T which are not necessarily distinct, and h is any hash function belonging to 'H picked uniformly at random. 1.1 Problem 1 Let us x a key a, E U. Let Y be the random variable that counts the number of keys in U (other than a, itself) that collide with a, under h. Bound the quantity Pr(Y 2 a) for some integer a 2 1 in terms of m, n, at using Markov's inequality. You may use the results obtained in the tutorial directly, but make sure you properly state the results rst. 1.2 Problem 2 Let a > E[Y]. Bound the quantity Pr(Y Z a) in terms of m, n, 0: using Cheby shev's inequality. Again, you may use results obtained in the tutorial directly. Hint: What is the relation between Pr(X 2 b) and Pr(|X | 2 b) when I) > 0? 1.3 Problem 3 We now continue a thread of discussion from the tutorial. Assume that the collisions are independent, i.e. keys aj,ak E U, 3' 7E k a 2' collide with i inde- pendently. Now bound Pr(Y 2 a) given a > E[Y] in terms of m,n,a using Chebyshev's inequality