随机算法 (Spring 2014)/Problem Set 1
Problem 1
(Due to J. von Neumann.)
- Suppose 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[\mbox{HEADS}]=\Pr[\mbox{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{ 1/(p(1-p)) }[/math].
- Devise an extension of the scheme that extracts the largest possible number of independent, unbiased coin-flips from a given number of flips of the biased coin.
Problem 2
(Due to D.E. Knuth and A. C-C. Yao.)
- Suppose you are provided with a source of unbiased random bits. Explain how you will use this to generate uniform samples from the set [math]\displaystyle{ S=\{0,\dots,n-1\} }[/math]. Determine the expected number of random bits required by your sampling algorithm.
- What is the worst-case number of random bits required by your sampling algorithm? Consider the case when [math]\displaystyle{ n }[/math] is a power of [math]\displaystyle{ 2 }[/math], as well as the case when it is not.
- Solve (1) and (2) when, instead of unbiased random bits, you are required to use as the source of randomness uniform random samples from the set [math]\displaystyle{ \{0,\dots,p-1\} }[/math]; consider the case when [math]\displaystyle{ n }[/math] is a power of [math]\displaystyle{ p }[/math], as well as the case when it is not.