随机算法 (Fall 2011)/Problem set 2

From EtoneWiki
Jump to: navigation, search

Problem 1

Some known facts:

  • Balls-into-bins: 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, uniformly and independently choose random bins and (might be the same bin), and throw the ball to the currently less loaded bin among bin and bin . 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.

  1. If we throw the first 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 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 power-of-two-choices. What is the asymptotic maximum load with high probability?

Problem 2

  1. Generalize the LazySelect algorithm for the general selection problem: finding the th smallest element in an array. Choose appropriate parameters to do the job.
  2. Use the Chernoff bounds instead of Chebyshev's inequality in the analysis of the above algorithm and try to use a smaller number of random samples.

Problem 3

The Monte Carlo method for computing

Suppose there are peoples, each wearing a hat. We collect all their hats and randomly distribute the hats back to them, with each people receiving exactly one hat. We ask for the probability that none of the people receives his/her own hat. We denote this probability by

Formally, a permutation is a bijection . A fixed point for permutation is an such that . Then is the probability that a uniformly random permutation has no fixed point. Such permutations are called derangements.

The derangement problem is taught in the undergraduate class Combinatorics at Nanjing University. See the lecture notes for details. By the Principle of Inclusion-Exclusion (容斥原则), we know that .

Recall that due to Taylor's expansion .

Now suppose you are given access to a balckbox which given as input a number , samples a uniform and independent permutation of , and returns true if has no fixed point and false if otherwise.

Give a randomized algorithm , whose inputs are and . The returned value of the algorithm should satisfy that

.
  • Your algorithm should call as subroutine. Try to make both and the number of times calling as small as possible.
  • Please give detailed analysis of your algorithm.