概率论 (Summer 2013)/Problem Set 1

Problem 1

(Due to J. von Neumann.)

1. Suppose you are given a coin for which the probability of HEADS, say [math]\displaystyle{ p }[/math], is unknown. How can you use this coin to generate unbiased (i.e., [math]\displaystyle{ \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]\displaystyle{ 1/(p(1-p)) }[/math].
2. 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

(Due to D.E. Knuth and A. C-C. Yao.)

1. 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]\displaystyle{ S=\{0,\dots,n-1\} }[/math]. Determine the expected number of random bits required by your sampling algorithm.
2. What is the worst-case number of random bits required by your sampling algorithm? Consider the case when [math]\displaystyle{ n }[/math] is a power of [math]\displaystyle{ 2 }[/math], as well as the case when it is not.
3. 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]\displaystyle{ \{0,\dots,p-1\} }[/math]; consider the case when [math]\displaystyle{ n }[/math] is a power of [math]\displaystyle{ p }[/math], as well as the case when it is not.

Problem 3

(Due to D.R. Karger and R. Motwani.)

1. 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\ne\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.
2. 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 4

(Due to R.M. 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, please devise a strategy to simulate random sampling with replacement from the original set of [math]\displaystyle{ n }[/math] balls. Notice that your only access to the balls is that you can sample without replacement from the bin.

说明：有的同学对于此题目的模型——也就是说允许做什么、不允许做什么，以及我们究竟要做什么 (-_-|||)——都不甚清楚。对此说明如下：

比方说我们能不断调用一个函数sample_from_bin()，每次从[math]\displaystyle{ d }[/math]个ball的bin里无放回随机采样一个ball，而这个bin里的[math]\displaystyle{ d }[/math]个ball，都是最初从[math]\displaystyle{ n }[/math]个ball里面无放回采样出来的。我们不知道[math]\displaystyle{ d }[/math]的大小（但可以知道[math]\displaystyle{ n }[/math]），只能对函数sample_from_bin()有一种“黑箱”式的访问。我们的目的是实现一个sample_from_balls()，每次调用都能返回一个从最初的[math]\displaystyle{ n }[/math]个ball里面有放回随机采样的ball。

这时最“傻”的办法就是第一次就不断的调用sample_from_bin()直到bin里面没有ball了，这个函数返回异常。这样我们就有了bin里面所有的ball，然后就也可以随便搞了。但假如[math]\displaystyle{ d }[/math]非常的大，而我们又希望每次运行我们的sample_from_balls()都只调用常数次sample_from_bin()，那么该如何做呢？

正如sample_from_bin()只能至多被调用[math]\displaystyle{ d }[/math]次，我们实现的这个sample_from_balls()至多可以被调用多少次呢？