### **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.

Course Home Page

cole@cs.nyu.edu (Richard Cole)

Last modified: Feb 13, 1997