随机算法 (Spring 2013)/Problem Set 1

From EtoneWiki
Jump to: navigation, search

第3题新增一问。由于是在作业发布之后修改,是否做这一问题不会影响分数,但增加此问会使该题目更有意义。

Problem 1

  • (Due to von Neumann) Suppose that you are given a coin for which the probability of HEADS, say , is unknown. How can you use this coin to generate unbiased (i.e., ) coin-flips? Give a scheme for which the expected number of flips of the biased coin for extracting one unbiased coin-flip is no more than .
  • (Due to Knuth and Yao) Supposed you are provided with a source of unbiased random bits. Explain how you will use this to generate uniform random samples from the set . Determine the expected number of bits required by your sampling algorithm. What is the worst-case number of bits required by your sampling algorithm (where the worst-case is taken over all random choices of unbiased random bits)? Consider the case when is a power of 2, as well as the case when it is not.

Problem 2

We play the following game:

Start with people, each with 2 hands. None of these hands hold each other. At each round, uniformly pick 2 free hands and let these two hands hold together. Repeat this until no free hands left.

  • What is the expected number of cycles made by people holding hands with each other (one person with left hand holding right hand is also counted as a cycle) at the end of the game?

(Hint: Consider how to count the number of cycles using indicator random variables.)

Problem 3

For any , a cut in an undirected graph is called an -min-cut if where is a min-cut in .

Give an analysis to lower bound the probability that a single iteration of Karger's Random Contraction algorithm returns an -min-cut in a graph of vertices.

  • 新增如下的一个问题。

Use the above bound to estimate the number of distinct -min cuts in .

Problem 4

Freivalds' Theorem
Let be an matrix such that . For a uniformly random ,
.
Schwartz-Zippel Theorem
Let be a multivariate polynomial of degree over a field such that . Fix any finite set , and let be chosen uniformly and independently at random from . Then

Prove that the Freivalds Theorem is a special case of the Schwartz-Zippel Theorem.

Problem 5

Consider the following two schemes of throwing balls into bins:

  • BiB (balls-into-bins):
for i=1 to m do:
  choose r uniformly and independently from [n];
  put ball-i into bin-r;

When , the maximum load is with high probability.

  • P2C (power-of-two-choices):
for i=1 to m do:
  choose r1 and r2 uniformly and independently from [n];
  if bin-r1 has fewer balls than bin-r2
      put ball-i into bin-r1;
  else
      put ball-i into bin-r2;

When , the maximum load is with high probability.

Questions: Assume balls are thrown to bins on after another.

  1. If we throw the first balls as BiB and then throw the rest balls as P2C, what is the asymptotic maximum load with high probability?
  2. If we throw the first balls as P2C and then throw the rest balls as BiB, what is the asymptotic maximum load with high probability?
  3. If we throw each even numbered ball as BiB and each odd numbered ball as P2C. What is the asymptotic maximum load with high probability?