imported>Zhangchihao |
imported>Zhangchihao |
Line 1: |
Line 1: |
| == Problem 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 == | | == Problem 2 == |
| (Due to D.E. Knuth and A. C-C. Yao.) | | Let <math>G(V,E)</math> be an undirected connected graph with maximum degree <math>\Delta</math> |
| | | * Design an efficient, time reversible, ergodic random walk on <math>G</math> whose stationary distribution is uniform distribution. |
| # 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.
| | * Let <math>\pi</math> be an arbitrary distribution on <math>V</math> such that <math>\pi(v)>0</math> for all <math>v\in V</math>. Design a time reversible, ergodic random walk on <math>G</math> whose stationary distribution is <math>\pi</math>. |
| # 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 == | | == 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 than some positive constant.
| |
|
| |
| == Problem 4 == | | == Problem 4 == |
| (Due to R.M. Karp)
| | == Problem 5 == |
| | |
| 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.
| |