随机算法 (Spring 2013)/Problem Set 2
(Due to Karp)
Consider a bin containing balls chosen at random (without replacement) from a collection of 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 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 balls have been drawn from the bin so far. Flip a coin with probability of HEADS being . If HEADS appears, then pick one of the 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 original balls. How many times can we repeat the sampling?
(Due to Karger and Motwani)
- Let be two disjoint subsets of a universe such that . Suppose we select a random set by independently sampling each element of with probability . We say that the random sample is good if the following two conditions hold: and . SHow that for , the probability that is good is larger than some positive constant.
- Suppose now that the random set is chosen by sampling the elements of with only pairwise independence. Show that for a suitable choice of the value of , the probability that is good is larger than some positive constant.
(Hint: Use the second moment.)
- (The hint for the second question was wrong. The second question is now optional and use whatever tools you can come up with.)
- Generalize the LazySelect algorithm for the -selection problem: Given as input an array of distinct numbers and an integer , find the 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.
(Generalization of Chernoff bound to the sum of geometric random variables.)
Let be independent geometrically distributed random variables each having expectation 2 (each of the is an independent experiment counting the number of tosses of an unbiased coin up to and including the first HEADS). Let and be a positive real constant. Use the moment generating functions to derive the best upper bound you can give on .