随机算法 (Spring 2013)/Problem Set 1: Difference between revisions
Jump to navigation
Jump to search
imported>Etone (Created page with "==Problem 1 (10 points)== * 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 unbias…") |
imported>Etone No edit summary |
||
| Line 1: | Line 1: | ||
==Problem 1 | ==Problem 1 == | ||
* 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>. | * 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>. | ||
== Problem 2 == | |||
We start with <math>n</math> 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? | |||
Revision as of 12:40, 11 March 2013
Problem 1
- 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].
Problem 2
We start with [math]\displaystyle{ n }[/math] 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?