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

Problem 1

• Suppose that you are given a coin for which the probability of HEADS, say $p$, is unknown. How can you use this coin to generate unbiased (i.e., $Pr[\mathrm{H}\mathrm{E}\mathrm{A}\mathrm{D}\mathrm{S}]=Pr[\mathrm{T}\mathrm{A}\mathrm{I}\mathrm{L}\mathrm{S}]=1/2$) 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 $\frac{1}{p(1-p)}$.

Problem 2

We start with $n$ people, each with 2 hands. None of these hands hold each other.

At each round, we uniformly pick 2 free hands and let them hold together.

• After how many rounds, there are 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 there are no free hands left?

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

Problem 3

For any $\alpha \ge 1$, a cut $C$ in an undirected graph $G(V,E)$is called an $\alpha$-min-cut if $|C|\le \alpha |C^{\ast }|$ where $C^{\ast }$ is a min-cut in $G$.

Give an analysis to lower bound the probability that a single iteration of Karger's Random Contraction algorithm returns an $\alpha$-min-cut in a graph $G(V,E)$ of $n$ vertices and $m$ edges.

Problem 4

Freivalds' Theorem

Let $A$ be an $n\times n$ matrix such that $A\ne \mathbf{0}$. For a uniformly random $r\in \{0,1{\}}^n$, $Pr[Ar=\mathbf{0}]\le \frac{1}{2}$.

Schwartz-Zippel Theorem

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

Prove that Schwartz-Zippel Theorem implies Freivalds Theorem.