Problem 5 (20 points). Consider the following generalization of Power of 2 choices to d > 2 choices: 1. Prepare d perfectly random hash functions hl, . . . 5 hd : U > [n]. 2. For each ball A, allocate it into the bin among his d choices {h1(A), . . . 5 hd(A)} with the lightest load at this moment. Suppose we are throwing 71 balls into n bins. Modify the proof given in lecture 2 to show that: With probability 1 n\More about the Power of 2-choice Max load of Gap between max-load m=O(n) balls and min-load of m = n(n log n) balls 1-choice hash m logn m n log log n) . log n n Power of 2-choice log log n + 0 loglogn + o (log log n)Chernoff bounds . Base case: m3 En/3 . Let us show my i-1 n X; with independent RVs X1, ..., Xn. If u = E[X], then Pr[X 2 (1 + 8)u] s e-82 M/3Wrap up . Back to bounding m4: since E[m4]