随机算法 (Spring 2013)/Problem Set 1: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
 
(12 intermediate revisions by the same user not shown)
Line 1: Line 1:
<font color=red size=5> 第3题新增一问。由于是在作业发布之后修改,是否做这一问题不会影响分数,但增加此问会使该题目更有意义。</font>
==Problem 1 ==
==Problem 1 ==
* (Due to von Neumann) Suppose that you are given a coin for which the probability of HEADS, say <math>p</math>, is ''unknown''. How can you use this coin to generate unbiased (i.e., <math>\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>\frac{1}{p(1-p)}</math>.
* (Due to von Neumann) Suppose that you are given a coin for which the probability of HEADS, say <math>p</math>, is ''unknown''. How can you use this coin to generate unbiased (i.e., <math>\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>\frac{1}{p(1-p)}</math>.
Line 5: Line 6:


== Problem 2 ==
== Problem 2 ==
We play the following game: Start with <math>n</math> people, each with 2 hands. None of these hands hold each other.
We play the following game:  
At each round, uniformly pick 2 free hands and let them 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), when the game ends?
Start with <math>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.)
('''Hint''': Consider how to count the number of cycles using indicator random variables.)
Line 15: Line 17:
For any <math>\alpha\ge 1</math>, a cut <math>C</math> in an undirected graph <math>G(V,E)</math>is called an <math>\alpha</math>-min-cut if <math>|C|\le\alpha|C^*|</math> where <math>C^*</math> is a min-cut in <math>G</math>.  
For any <math>\alpha\ge 1</math>, a cut <math>C</math> in an undirected graph <math>G(V,E)</math>is called an <math>\alpha</math>-min-cut if <math>|C|\le\alpha|C^*|</math> where <math>C^*</math> is a min-cut in <math>G</math>.  


Give an analysis to lower bound the probability that a single iteration of Karger's Random Contraction algorithm returns an <math>\alpha</math>-min-cut in a graph <math>G(V,E)</math> of <math>n</math> vertices and <math>m</math> edges.
Give an analysis to lower bound the probability that a single iteration of Karger's Random Contraction algorithm returns an <math>\alpha</math>-min-cut in a graph <math>G(V,E)</math> of <math>n</math> vertices.
 
*<font color=red font=3>新增如下的一个问题。</font>
 
Use the above bound to estimate the number of distinct <math>\alpha</math>-min cuts in <math>G</math>.


== Problem 4 ==
== Problem 4 ==
Line 33: Line 39:
Consider the following two schemes of throwing <math>m</math> balls into <math>n</math> bins:
Consider the following two schemes of throwing <math>m</math> balls into <math>n</math> bins:
*BiB (balls-into-bins):
*BiB (balls-into-bins):
  for i=1 to m do
  for i=1 to m do:
   choose r uniformly and independently from [n];
   choose r uniformly and independently from [n];
   put ball-i into bin-r;
   put ball-i into bin-r;
When <math>m=\Theta(n)</math>, the maximum load is <math>\Theta\left(\frac{\ln n}{\ln\ln n}\right)</math> with high probability.
When <math>m=\Theta(n)</math>, the maximum load is <math>\Theta\left(\frac{\ln n}{\ln\ln n}\right)</math> with high probability.
* P2C (power of two choices):  
* P2C (power-of-two-choices):  
  for i=1 to m do
  for i=1 to m do:
   choose r1 and r2 uniformly and independently from [n];
   choose r1 and r2 uniformly and independently from [n];
   if bin-r1 has fewer balls than bin-r2
   if bin-r1 has fewer balls than bin-r2
Line 48: Line 54:
Questions: Assume <math>n</math> balls are thrown to <math>n</math> bins on after another.
Questions: Assume <math>n</math> balls are thrown to <math>n</math> bins on after another.
# If we throw the first <math>\frac{n}{2}</math> balls as BiB and then throw the rest balls as P2C, what is the asymptotic maximum load with high probability?
# If we throw the first <math>\frac{n}{2}</math> balls as BiB and then throw the rest balls as P2C, what is the asymptotic maximum load with high probability?
# If we throw the first <math>\frac{n}{2}</math> balls as P2C and then throw the rest balls as BiB, what is the asymptotic maximum load with high probability?
# 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?
# 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?

Latest revision as of 03:49, 21 March 2013

第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 distinct [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?