概率论 (Summer 2013) and 概率论 (Summer 2013)/Problem Set 1: Difference between pages
imported>Zhangchihao No edit summary |
imported>Zhangchihao mNo edit summary |
||
Line 1: | Line 1: | ||
== Problem 1 == | |||
(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</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 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. | |||
== Problem 3 == | |||
(Due to D.R. Karger and R. Motwani.) | |||
# Let <math>S,T</math> be two disjoint subsets of a universe <math>U</math> such that <math>|S|=|T|=n</math>. Suppose we select a random set <math>R\subseteq U</math> by independently sampling each element of <math>U</math> with probability <math>p</math>. We say that the random sample <math>R</math> is <i>good</i> if the following two conditions hold: <math>R\cap S=\emptyset</math> and <math>R\cap T\ne\emptyset</math>. Show that for <math>p=1/n</math>, the probability that <math>R</math> is good is larger than some positive constant. | |||
# Suppose now that the random set <math>R</math> is chosen by sampling the elements of <math>U</math> with only <i>pairwise</i> independence. Show that for a suitable choice of the value of <math>p</math>, the probability that <math>R</math> is good is larger than some positive constant. | |||
== Problem 4 == | |||
(Due to R.M. Karp) | |||
Consider a bin containing <math>d</math> balls chosen at random (without replacement) from a collection of <math>n</math> distinct balls. Without being able to see or count the balls in the bin, please devise a strategy to simulate random sampling <i>with replacement</i> from the original set of <math>n</math> balls. Notice that your only access to the balls is that you can sample <i>without replacement</i> from the bin. | |||
== Problem 5 == | |||
We play the following game: | |||
Start with <math>n</math> people, each with 2 hands. None of these hands hold each other. At each round, uniformly pick 2 free hands and let these two hands hold together. Repeat this until 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) at the end of the game? |
Revision as of 05:45, 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.
Problem 3
(Due to D.R. Karger and R. Motwani.)
- Let [math]\displaystyle{ S,T }[/math] be two disjoint subsets of a universe [math]\displaystyle{ U }[/math] such that [math]\displaystyle{ |S|=|T|=n }[/math]. Suppose we select a random set [math]\displaystyle{ R\subseteq U }[/math] by independently sampling each element of [math]\displaystyle{ U }[/math] with probability [math]\displaystyle{ p }[/math]. We say that the random sample [math]\displaystyle{ R }[/math] is good if the following two conditions hold: [math]\displaystyle{ R\cap S=\emptyset }[/math] and [math]\displaystyle{ R\cap T\ne\emptyset }[/math]. Show that for [math]\displaystyle{ p=1/n }[/math], the probability that [math]\displaystyle{ R }[/math] is good is larger than some positive constant.
- Suppose now that the random set [math]\displaystyle{ R }[/math] is chosen by sampling the elements of [math]\displaystyle{ U }[/math] with only pairwise independence. Show that for a suitable choice of the value of [math]\displaystyle{ p }[/math], the probability that [math]\displaystyle{ R }[/math] is good is larger than some positive constant.
Problem 4
(Due to R.M. Karp)
Consider a bin containing [math]\displaystyle{ d }[/math] balls chosen at random (without replacement) from a collection of [math]\displaystyle{ n }[/math] distinct balls. Without being able to see or count the balls in the bin, please devise a strategy to simulate random sampling with replacement from the original set of [math]\displaystyle{ n }[/math] balls. Notice that your only access to the balls is that you can sample without replacement from the bin.
Problem 5
We play the following game:
Start with [math]\displaystyle{ n }[/math] people, each with 2 hands. None of these hands hold each other. At each round, uniformly pick 2 free hands and let these two hands hold together. Repeat this until 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) at the end of the game?