# 随机算法 (Spring 2013)/Problem Set 2

- 注意写明自己的姓名与学号。
- 必须包含完整的解题过程，中英文不限。

## Contents

## Problem 1

(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?

## Problem 2

(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
independence. Show that for a suitable choice of the value of , the probability that is good is larger than some positive constant.**pairwise**~~(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.)

## Problem 3

- 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.

## Problem 4

(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 .