概率论 (Summer 2013)/Problem Set 1: Difference between revisions
Jump to navigation
Jump to search
imported>Zhangchihao No edit summary |
imported>Zhangchihao No edit summary |
||
| Line 1: | Line 1: | ||
== Problem 1 == | == Problem 1 == | ||
(Due to J. von Neumann) | (Due to J. von Neumann.) | ||
# Suppose you are given a coin for which the probability of HEADS, say <math>p</math>, is <i>unknown</i> | # Suppose you are given a coin for which the probability of HEADS, say <math>p</math>, is <i>unknown</i>. How can you use this coin to generate unbiased (i.e., <math>\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>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 | |||
Revision as of 05:23, 4 July 2013
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