Randomized Algorithms (Spring 2010)/Problem Set 2

Problem 1 (10 points)

Some known facts:

• Balls-into-bins: [math]\displaystyle{ m }[/math] balls are uniformly and independently thrown to [math]\displaystyle{ n }[/math] bins. If [math]\displaystyle{ m=\Theta(n) }[/math], then the maximum load is [math]\displaystyle{ \Theta\left(\frac{\ln n}{\ln\ln n}\right) }[/math] with high probability.
• Power of two choices: [math]\displaystyle{ m }[/math] balls are sequentially thrown to [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ m=\Theta(n) }[/math], after all [math]\displaystyle{ m }[/math] balls are thrown to bins, the maximum load is [math]\displaystyle{ \Theta\left(\ln \ln n\right) }[/math] with high probability.

Questions: Assume [math]\displaystyle{ n }[/math] balls and [math]\displaystyle{ n }[/math] bins. We throw the [math]\displaystyle{ n }[/math] balls sequentially.

1. If we throw the first [math]\displaystyle{ \frac{n}{2} }[/math] balls uniformly and then throw the rest balls as the way of power-of-two-choices, what is the asymptotic maximum load with high probability?
2. For the [math]\displaystyle{ k }[/math]th ball, if [math]\displaystyle{ k }[/math] is even, we throw the ball to a uniform bin; and if [math]\displaystyle{ k }[/math] is odd, we throw the ball as the way of power-of-two-choices. What is the asymptotic maximum load with high probability?

Problem 2 (10 points)

Suppose that we flip a fair coin [math]\displaystyle{ n }[/math] times to obtain [math]\displaystyle{ n }[/math] random bits. Consider all [math]\displaystyle{ m={n\choose 2} }[/math] pairs of these bits in some order. Let [math]\displaystyle{ Y_i }[/math] be the exclusive-or of the [math]\displaystyle{ i }[/math]th pair of bits, and let [math]\displaystyle{ Y=\sum_{i=1}^m Y_i }[/math] be the number of [math]\displaystyle{ Y_i }[/math] that equal 1.

1. Show that the [math]\displaystyle{ Y_i }[/math] are NOT mutually independent.
2. Show that the [math]\displaystyle{ Y_i }[/math] satisfy the property [math]\displaystyle{ \mathbf{E}[Y_iY_j]=\mathbf{E}[Y_i]\mathbf{E}[Y_j] }[/math].
3. Compute [math]\displaystyle{ \mathbf{Var}[Y] }[/math].
4. Using Chebyshev's inequality, prove a bound on [math]\displaystyle{ \Pr[|Y-\mathbf{E}[Y]|\ge n] }[/math].

Problem 3 (10 points)

The class BPP (for Bounded-error Probabilistic Polynomial time) is defined as follows:

Definition: The class BPP consists of all decision problems [math]\displaystyle{ f }[/math] that have a randomized algorithm [math]\displaystyle{ A }[/math] running in worst-case polynomial time such that for any input [math]\displaystyle{ x }[/math], if [math]\displaystyle{ f(x)=1 }[/math], then [math]\displaystyle{ \Pr[A(x)=1]\ge 1-1/4 }[/math]; if [math]\displaystyle{ f(x)=0 }[/math], then [math]\displaystyle{ \Pr[A(x)=0]\ge 1-1/4 }[/math].

We can generalize this definition to other value of errors and define the parameterized classes BPP[math]\displaystyle{ (\epsilon) }[/math].

Definition: The class BPP[math]\displaystyle{ (\epsilon) }[/math] consists of all decision problems [math]\displaystyle{ f }[/math] that have a randomized algorithm [math]\displaystyle{ A }[/math] running in worst-case polynomial time such that for any input [math]\displaystyle{ x }[/math], if [math]\displaystyle{ f(x)=1 }[/math], then [math]\displaystyle{ \Pr[A(x)=1]\ge 1-\epsilon }[/math]; if [math]\displaystyle{ f(x)=0 }[/math], then [math]\displaystyle{ \Pr[A(x)=0]\ge 1-\epsilon }[/math].

So the original BPP is actually BPP[math]\displaystyle{ (1/4) }[/math].

• Prove that BPP[math]\displaystyle{ (\epsilon) }[/math] is the same for all [math]\displaystyle{ \frac{1}{2^n}\le\epsilon\le\frac{1}{2}-\frac{1}{p(n)} }[/math], for a polynomial [math]\displaystyle{ p(n) }[/math] of the input size [math]\displaystyle{ n }[/math].

The solution of this problem gives a very simple scheme for boosting the accuracy of Monte Carlo randomized algorithms with two-sided 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 [math]\displaystyle{ n }[/math] elements in linear time with high probability ([math]\displaystyle{ 1-o(1) }[/math]).

For the convenience, you are allowed to ignore the effects of the floors ([math]\displaystyle{ \lfloor\cdot\rfloor }[/math]) and ceilings ([math]\displaystyle{ \lceil\cdot\rceil }[/math]).

Problem 5 (10 points)

In many wireless communication systems, each receiver listens on a specific frequency. The bit [math]\displaystyle{ b(t) }[/math] sent at time [math]\displaystyle{ t }[/math] is represented by a [math]\displaystyle{ 1 }[/math] or [math]\displaystyle{ -1 }[/math]. Unfortunately, noise from other nearby communications can affect the receiver's signal. A simplified model of this noise is as follows. There are [math]\displaystyle{ n }[/math] other senders, and the [math]\displaystyle{ i }[/math]th has strength [math]\displaystyle{ p_i\le 1 }[/math]. At any time [math]\displaystyle{ t }[/math], the [math]\displaystyle{ i }[/math]th sender is also trying to send a bit [math]\displaystyle{ b_i(t) }[/math] that is represented by [math]\displaystyle{ 1 }[/math] or [math]\displaystyle{ -1 }[/math]. The receiver obtains the signal [math]\displaystyle{ s(t) }[/math] given by

[math]\displaystyle{ s(t)=b(t)+\sum_{i=1}^np_ib_i(t) }[/math].

If [math]\displaystyle{ s(t)\gt 0 }[/math], then the receiver assumes that the bit sent at time [math]\displaystyle{ t }[/math] was 1; otherwise, the receiver assumes that it was -1.

Assume that all the bits [math]\displaystyle{ b_i(t) }[/math] can be considered independent, uniform random variables. Give a Chernoff bound to estimate the probability that the receiver makes an error in determining [math]\displaystyle{ b(t) }[/math].