随机算法 (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

(DUe to Karger and 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\neq\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 3

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