### Homework 4, Randomized Algorithms

Due date: March 4.

All references are to the course text.

Page 64, Exercise 3.3.
Hint. What is the probability that a memory module receives no requests? One request?

Page 64, problem 3.4.
Notation. x^y denotes x to the power of y.
Hint. Suppose there are at most n/2^j balls at the start of a round. Upper bound the probability that a given ball collides, and apply the Chebyshev Inequality to show that with high probability at most 2n/4^j balls collide.
For j<2, show that with high probability the number of balls surviving is reduced by at least n/4 in one iteration.
Another special case calculation is required when there are at most n^{3/4} balls.

Alternative hint. Suppose there are at most n/2^j balls at the start of a round, j>1. Show that the expected number of balls at the start of the next round is at most n/4^j. Use Markov's Inequality to show that there are at most 2n/4^j balls at the start of the next round with probability at least 1/2, and call this a good event. Similarly, show that with probability at least 1/3 the number of balls is reduced from n to at most 3/4 n in the first round (and hence with probability at least 1/2 in two rounds), and again with probability 1/3 from at most (3/4)^i n to at most (3/4)^{i+1} n in one round (and hence with probability at least 1/2 in two rounds). Call these pairs of rounds good events if the specified reduction occurs. After log log n + 5 good events there are no balls left. Using Chebyshev's Inequality, show that with probability 1 - o(1) there are at most c log log n rounds, for some constant c. (The random variables are defined according to whether events are good or not.)

Page 64, problem 3.5.
Hint. Consider Y=(X-E[X]+c sigma_X)^2, and choose c appropriately. Assume sigma_X is non-zero.

cole@cs.nyu.edu (Richard Cole)