6.856 — Randomized Algorithms David Karger Handout #4, September 17, 2002 — Homework 1 Solutions Problem 1 MR 1.1. (a) We rely on the fact that flips are independent, even if biased. To try to generate one bit, flip the coin twice. If you get heads followed by tails (HT) then output heads. If tails followed by heads (TH) output tails. If HH or TT, report failure. Conditioned on having succeeded (gotten HT or TH) the probability that you got HT is equal to the probability you got TH, so the output you produce is unbiased. If you fail, you try again, repeating until you succeed. The probability that you succeed in one trial is just 2p(1 − p) (probability of one head and one tail). So the number of trials you perform before succeeding has a geometric distribution; its expectation is 1/[2p(1 − p)]. Since we toss the coin twice at each trial, the expected number of total coin tosses is 1/[p(1 − p)]. (b) The following solution owes to [Elias72]. This one is tricky. Any reasonable effort is sufficient for full credit. Before we tackle the problem itself, let us consider the following scenario: suppose you are given a number r drawn uniformly at random from {1, . . . , N}. How many unbiased bits can you output from such a sample? The following scheme will turn out to be asymptotically optimal: Suppose that the binary representation of N is as follows: N = αm2m + αm−12m−1 + · · · + α121 + α020 , where αi ∈ {0, 1}, αm = 1, and m = �log N�. We assign output strings to the N numbers, so that for every i > 0 with αi = 1, we map 2i of the numbers to all the binary strings of length i. The exact assignment does not matter, but since every input number is equally likely, we are assured that the output bits are unbiased and independent random bits. Note that if N is odd, i.e. α0 = 1, one of the input numbers will not be assigned to any output – if we encounter it, we output nothing. Luckily, this case will become increasingly unlikely as N grows. It remains to be seen how many bits we expect to output using this scheme. Due to the above construction, if αi = 1 for some i > 0, then we output a length i bit string with 1 M.R. refers to this text:Motwani, Rajeez, and Prabhakar Raghavan. Randomized Algorithms. Cambridge: Cambridge University Press, 1995.� � � � � � � � � � � � � � � � � � probability 2i/N . So the expected output length is equal to m� 2i EN := E [ # bits output ] = i · αi · N i=0 mm�1 � (m − i) · αi · 2i = Nm · αi · 2i − i=0 i=0 m1 � = m − (m − i) · αi · 2i N i=0 − m ≤ 2m+1We have N ≥ 2m, and (m − i)αi2i (m − i)2i = 2m+1 . This implies ≤ 2m+1 log N ≥ m ≥ EN = m − 2 ≥ log N − 3≥ m − 2m Let us now apply this observation to the problem we really want to solve, extracting bits from n biased coin flips. Suppose we flip the coin n times and see k heads. There are n different different positions those k heads can take among the n flips (that is, which k of the k flips came up heads), and each is equally likely. So, using the above scheme, nwe can map them to bit sequences with an expected length of about log k . Since the nprobability that we see k heads is pk (1 − p)n−k , we can conclude that the expected k number E of output bits is n� p k (1 − p)n−k � n k � log � n k � − 3 ≤ E ≤ n� p k (1 − p)n−k � n k � log � n k � (1) k=0 k=0 To bound this quantity will use the following two facts: Fact 1 (Weak law for binomial distributions) For all p ∈ [0, 1], ε > 0 there exists n0 ∈ N, such that for all n ≥ n0, a (1 − ε) fraction of all length n sequences of p-biased coin flips contain between n(p − ε) and n(p + ε) heads. � Fact 2 1 n 1 1 lim log = H (p) := p · log + (1 − p) · log � n n · p p 1 − pn→∞ This second fact follows easily from log n! ≈ n log n – a consequence of Stirling’s Formula; see Proposition B.1 in the MR book. nThis first fact implies that (1) asymptotically grows like log np , 1 which according to 1More precisely, that n n(1 − ε) · min log n(p + α) − 3 ≤ E ≤ (1 + ε) · max log |α|≤ε |α|≤ε n(p + α) . 2� � � � � � � � the second fact converges to nH(p),2 which proves that our scheme obtains the optimum expected output length. (c) This is a (the) classic result from information theory [Shannon48]. The basic idea behind the proof is the following. By Fact 1 from part (b), we know that as n becomes large, almost all sequences have about np heads in them. So the input can be approximated nby just np sequences of equal probability. The ‘best’ we can do to get unbiased bits is to map all of these sequences to different output strings from some {0, 1}k . Since we nonly have np sequences to map from, we have that k ≤ log n , which by Fact 2 from np above implies that k ≤ nH(p) in the limit. Problem 2 MR 1.5. (a) Let’s partition the unit interval into n intervals Ii of length pi. If we could generate a number U chosen uniformly at random from the unit interval, then it would fall into interval Ii with probability pi, so we could output item i in that case. Since we don’t want to generate the infinitely many bits needed to specify a number in the unit interval, we perform a lazy evaluation, generating only as long a prefix of U as we need to be certain that U falls in a particular interval Ii (this can be thought of as an application of the principle of deferred decision: we generate all the bits of U , but the only examine as many as we need to make a decision). To decide how many bits of U we will generate/look at, let us consider the probability that we will need to generate more than k bits. Suppose we have generated k bits of U , call them Uk . Based on Uk , we know that U lies in a particular one of 2k equal-length subintervals of the unit interval, call it V . If this subinterval V is contained in one of the …