# 随机算法 (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 , 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 ,
- .

- 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

- 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.

- 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?
- 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?
- 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?