随机算法 (Spring 2013)/Problem Set 2
Problem 1
(Due to 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, we would like to simulate random sampling with replacement from the original set of [math]\displaystyle{ n }[/math] balls. Our only access to the balls in that we can sample without replacement from the bin.
(Spoiler alert: You may want to stop here for a moment and start thinking about the solution before proceeding to read the following part.)
Consider the following strategy. Suppose that [math]\displaystyle{ k\lt d }[/math] balls have been drawn from the bin so far. Flip a coin with probability of HEADS being [math]\displaystyle{ k/n }[/math]. If HEADS appears, then pick one of the [math]\displaystyle{ k }[/math] previously drawn balls uniformly at random; otherwise, draw a random ball from the bin. Show that each choice is independently and uniformly distributed over the space of the [math]\displaystyle{ n }[/math] original balls. How many times can we repeat the sampling?
Problem 2
- Generalize the LazySelect algorithm for the [math]\displaystyle{ k }[/math]-selection problem: Given as input an array of [math]\displaystyle{ n }[/math] distinct numbers and an integer [math]\displaystyle{ k }[/math], find the [math]\displaystyle{ k }[/math]th smallest number in the array.
- Use the Chernoff bounds instead of Chebyshev's inequality in the analysis of the LazySelect Algorithm and try to use as few random samples as possible.