Randomized Algorithms (Spring 2010)/Problem Set 2
Contents
Problem 1 (10 points)
Some known facts:
 Ballsintobins: balls are uniformly and independently thrown to bins. If , then the maximum load is with high probability.
 Power of two choices: balls are sequentially thrown to bins. For each ball, choose two uniform random bins, and throw the ball to the current less loaded bin among the two chosen bins. Assuming that , after all balls are thrown to bins, the maximum load is with high probability.
Questions: Assume balls and bins. We throw the balls sequentially.
 If we throw the first balls uniformly and then throw the rest balls as the way of poweroftwochoices, what is the asymptotic maximum load with high probability?
 For the th ball, if is even, we throw the ball to a uniform bin; and if is odd, we throw the ball as the way of poweroftwochoices. What is the asymptotic maximum load with high probability?
Problem 2 (10 points)
Suppose that we flip a fair coin times to obtain random bits. Consider all pairs of these bits in some order. Let be the exclusiveor of the th pair of bits, and let be the number of that equal 1.
 Show that the are NOT mutually independent.
 Show that the satisfy the property .
 Compute .
 Using Chebyshev's inequality, prove a bound on .
Problem 3 (10 points)
The class BPP (for Boundederror Probabilistic Polynomial time) is defined as follows:
Definition: The class BPP consists of all decision problems that have a randomized algorithm running in worstcase polynomial time such that for any input ,

We can generalize this definition to other value of errors and define the parameterized classes BPP.
Definition: The class BPP consists of all decision problems that have a randomized algorithm running in worstcase polynomial time such that for any input ,

So the original BPP is actually BPP.
 Prove that BPP is the same for all , for a polynomial of the input size .
The solution of this problem gives a very simple scheme for boosting the accuracy of Monte Carlo randomized algorithms with twosided errors.
Problem 4 (10 points)
Random sampling is expensive. Redesign the parameters of the LazySelect algorithm for median selection to sample as small number of elements as possible. Use the Chernoff bound to show that your algorithm finds the median of elements in linear time with high probability ().
For the convenience, you are allowed to ignore the effects of the floors () and ceilings ().
Problem 5 (10 points)
In many wireless communication systems, each receiver listens on a specific frequency. The bit sent at time is represented by a or . Unfortunately, noise from other nearby communications can affect the receiver's signal. A simplified model of this noise is as follows. There are other senders, and the th has strength . At any time , the th sender is also trying to send a bit that is represented by or . The receiver obtains the signal given by
 .
If , then the receiver assumes that the bit sent at time was 1; otherwise, the receiver assumes that it was 1.
Assume that all the bits can be considered independent, uniform random variables. Give a Chernoff bound to estimate the probability that the receiver makes an error in determining .