概率论 (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 2: | Line 2: | ||
(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>. How can you use this coin to generate unbiased (i.e., <math>\Pr[\mbox{HEADS}]=\Pr[\mbox{TAILS}=1/2 | # 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. | # 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. | ||
Line 9: | Line 8: | ||
(Due to D.E. Knuth and A. C-C. Yao.) | (Due to D.E. Knuth and A. C-C. Yao.) | ||
# Suppose | # 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>S=\{0,\dots,n-1\}</math>. Determine the expected number of random bits required by your sampling algorithm. | ||
# What is the <i>worst-case</i> number of random bits required by your sampling algorithm? Consider the case when <math>n</math> is a power of <math>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>\{0,\dots,p-1\}</math>; consider the case when <math>n</math> is a power of <math>p</math>, as well as the case when it is not. |
Revision as of 05:28, 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 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.