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

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

Problem 1

• (Due to von Neumann) Suppose that you are given a coin for which the probability of HEADS, say [math]\displaystyle{ p }[/math], is unknown. How can you use this coin to generate unbiased (i.e., [math]\displaystyle{ \Pr[\mathrm{HEADS}]=\Pr[\mathrm{TAILS}]=1/2 }[/math]) 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 [math]\displaystyle{ \frac{1}{p(1-p)} }[/math].

• (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 [math]\displaystyle{ [n]=\{0,1,\ldots,n-1\} }[/math]. 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 [math]\displaystyle{ n }[/math] is a power of 2, as well as the case when it is not.

Problem 2

We play the following game:

Start with [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ \alpha\ge 1 }[/math], a cut [math]\displaystyle{ C }[/math] in an undirected graph [math]\displaystyle{ G(V,E) }[/math]is called an [math]\displaystyle{ \alpha }[/math]-min-cut if [math]\displaystyle{ |C|\le\alpha|C^*| }[/math] where [math]\displaystyle{ C^* }[/math] is a min-cut in [math]\displaystyle{ G }[/math].

Give an analysis to lower bound the probability that a single iteration of Karger's Random Contraction algorithm returns an [math]\displaystyle{ \alpha }[/math]-min-cut in a graph [math]\displaystyle{ G(V,E) }[/math] of [math]\displaystyle{ n }[/math] vertices.

• 新增如下的一个问题。

Use the above bound to estimate the number of [math]\displaystyle{ \alpha }[/math]-min cuts in [math]\displaystyle{ G }[/math].

Problem 4

Freivalds' Theorem

Let [math]\displaystyle{ A }[/math] be an [math]\displaystyle{ n\times n }[/math] matrix such that [math]\displaystyle{ A\neq\boldsymbol{0} }[/math]. For a uniformly random [math]\displaystyle{ r \in\{0, 1\}^n }[/math], [math]\displaystyle{ \Pr[Ar = \boldsymbol{0}]\le \frac{1}{2} }[/math].

Schwartz-Zippel Theorem

Let [math]\displaystyle{ f\in\mathbb{F}[x_1,x_2,\ldots,x_n] }[/math] be a multivariate polynomial of degree [math]\displaystyle{ d }[/math] over a field [math]\displaystyle{ \mathbb{F} }[/math] such that [math]\displaystyle{ f\not\equiv 0 }[/math]. Fix any finite set [math]\displaystyle{ S\subset\mathbb{F} }[/math], and let [math]\displaystyle{ r_1,r_2\ldots,r_n }[/math] be chosen uniformly and independently at random from [math]\displaystyle{ S }[/math]. Then [math]\displaystyle{ \Pr[f(r_1,r_2,\ldots,r_n)=0]\le\frac{d}{|S|}. }[/math]

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

Problem 5

Consider the following two schemes of throwing [math]\displaystyle{ m }[/math] balls into [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ m=\Theta(n) }[/math], the maximum load is [math]\displaystyle{ \Theta\left(\frac{\ln n}{\ln\ln n}\right) }[/math] 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 [math]\displaystyle{ m=\Theta(n) }[/math], the maximum load is [math]\displaystyle{ \Theta\left(\ln \ln n\right) }[/math] with high probability.

Questions: Assume [math]\displaystyle{ n }[/math] balls are thrown to [math]\displaystyle{ n }[/math] bins on after another.

1. If we throw the first [math]\displaystyle{ \frac{n}{2} }[/math] 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 [math]\displaystyle{ \frac{n}{2} }[/math] 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?