6.046J Lecture 9: Randomized Algorithms II

Lecture 9 Randomized Algorithms II Supplemental reading in CLRS: Appendix C; Section 7.3 After Lecture 8, several students asked whether it was fair to compare randomized algorithms to deterministic algorithms. Determistic algorithm: • always outputs the right answer • always runs efficiently Randomized algorithm: • may sometimes not output the right answer • may sometimes not run efficiently Is this “fair”? Of course not. We demand less from randomized algorithms. But in exchange, we expect randomized algorithms to do more—to be more efficient, or to be simple and elegant. Separately, we might ask whether it is useful to employ randomized algorithms. The answer here is that it depends: • on the situation • on the available alternatives • on the probability of error or inefficiency. Lots of real-life situations call for randomized algorithms. For example, Google Search and IBM’s Jeopardy!-playing computer Watson both employ randomized algorithms. 9.1 The Central Limit Theorem and the Chernoff Bound Ideally, a randomized algorithm will have the property that £ ¤ n→∞ Pr bad things happening −−−−→ 0. Before further analyzing randomized algorithms, it will be useful to establish two basic facts about probability theory: the central limit theorem and the Chernoff bound. The central limit theorem states that the mean of a large number of independent copies of a random variable is approximately normal, as long as the variable has finite variance. The normal distribution (or Gaussian distribution) of mean 0 and variance 1, denoted N(0, 1), is defined by the probability density function ¡ ± ¢ 1 f N(0,1) (x) = p exp − x2 2 . 2π Figure 9.1. A tail of the normal distribution. Taking an affine transform of this standard Gaussian, we obtain the normal distribution with arbi¡ ¢ trary mean µ and arbitrary variance σ2 , denoted N µ, σ2 . Its probability density function is µ ¶ (x − µ)2 1 exp − . f N (µ,σ2 ) (x) = p 2σ2 2πσ2 Due in part to the following theorem, the Gaussian distribution is extremely important in all of probability theory. Theorem 9.1 (Central Limit Theorem). Suppose X 1 , X 2 , . . . are i.i.d.1 random variables, each with ¢ p ¡ +X n finite mean µ and finite variance σ2 . Let S n = X 1 +... , and let Yn = n S n − µ . Then the variables n Y1 , Y2 , . . . converge to a normal distribution: ¡ ¢ d Yn − → N 0, σ2 . The precise meaning of this theorem is somewhat technical. Again, in effect it means that the average of a large number of independent copies of a random variable X is approximately normally distributed. Thus, the probability that this average exceeds its expected value by r is approximately the probability that a normal random variable with variance σ2 exceeds its expected value by r. While this heuristic reasoning does not rigorously prove any specific bound, there are a number of bounds that have been worked out for certain common distributions of X . One such bound is the Chernoff bound, one version of which is as follows: Theorem 9.2 (Chernoff bound). Let Y ∼ B(n, p) be a random variable representing the total number of heads in a series of n independent coin flips, where each flip has probability p of coming up heads. Then, for all r > 0, we have h i ¡ ± ¢ Pr Y ≥ E [Y ] + r ≤ exp −2r 2 n . The distribution in Theorem 9.2 is called the binomial distribution with parameters (n, p). ¡n¢ m The probability of m heads is m p (1 − p)n−m . There are several different versions of the Chernoff bound—some with better bounds for specific hypotheses, some more general. Section C.5 of CLRS gives a classic proof of the Chernoff bound, ¡ ¢ applying the Markov inequality to the random variable exp α(Y − E [Y ]) for a suitable constant α. We give a different proof here2 , due to Impagliazzo and Kabanets, 2010. 1 independent and identically distributed 2 Of a different theorem, actually. The version we prove here is (stronger than) Exercise C.5-6 of CLRS. Lec 9 – pg. 2 of 9 0 1 2 3 4 5 6 Figure 9.2. Galton’s board is a toy in which, at each peg, the ball has probability 12 of moving left and probability 21 of moving right. The number of the bin into which it falls is a binomial random variable with parameters (n, 12 ). If n is large and you drop a large number of balls into the board, the collection of balls in the bins underneath will start to look like a Gaussian probability density curve. Lec 9 – pg. 3 of 9 Proof of Theorem 9.2. Let Y = X1 + · · · + X n, where X 1 , . . . , X n are independent {0, 1}-valued random variables, each having probability p of being 1. Thus Y is a binomial random variable with parameters (n, p). Let S be a random subset of {1, . . . , n} such that each element of {1, . . . , n} independently has probability q of being included in S, where q is a parameter that will be determined later. The probability that X i = 1 for all i ∈ S is " # " # ¯ h i ^ ^ ¯ Pr X i = 1 = Pr X i = 1 ¯ Y ≥ E [Y ] + r Pr Y ≥ E [Y ] + r i ∈S i ∈S " # h i ^ ¯¯ + Pr ¯ Y < E [Y ] + r Pr Y < E [Y ] + r i ∈S " # ¯ h i ¯ X i = 1 ¯ Y ≥ E [Y ] + r Pr Y ≥ E [Y ] + r . ^ ≥ Pr i ∈S (9.1) Meanwhile, " Pr ^ i ∈S # ¯ ¯ X i = 1 ¯ Y ≥ E [Y ] + r ≥ (1 − q)n−(E [Y ]+r) , (9.2) V since the condition i∈S X i = 1 is equivalent to the condition that S doesn’t include the indices of any zeros, and we are conditioning on the hypothesis that there are at most n − (E [Y ] + r) zeros. (This is the “key idea” of the proof. Notice that we have switched from conditioning on S followed by the X i ’s to conditioning on the X i ’s followed by S.) Combining (9.1) and (9.2), we obtain " # h i ^ Pr X i = 1 ≥ (1 − q)n−(E [Y ]+r) Pr Y ≥ E [Y ] + r . (9.3) i ∈S £V ¤ We could also compute Pr i∈S X i = 1 by conditioning on S in a different way: " # ´ ´ ³ n ³¡ ¢ X ^ n k k n− k · p . Pr Xi = 1 = q (1 − q) k | {z } {z } i ∈S k=0 | ¯ i h h i Pr |S |= k Pr V i ∈S ¯ X i =1 ¯ |S |= k Recall the binomial formula, which states (a + b)n = n ¡ ¢ X n k=0 k a k b n− k . In the present case, we have " Pr # ¡ ¢n Xi = 1 = qp +1− q . ^ (9.4) i ∈S Combining (9.3) and (9.4), we obtain h i ¡ ¢n (1 − q)n−(E [Y ]+r) Pr Y ≥ E [Y ] + r ≤ q p + 1 − q . Rearranging and using the fact that E [Y ] = np, we have equivalently ¡ ¢n h i qp +1− q . Pr Y ≥ E [Y ] + r ≤ (1 − q)n−(np+r) Lec 9 – pg. 4 of 9 (9.5) Equation (9.5) holds for arbitrary q, so we might as well assign a value to q for which the right side is minimal. Let r/n ¢ q= ¡ ; r p + n (1 − p) after some expansion, the right side of (9.5) becomes à !1−( p+ r ) n ! p+ r à n n ¡ ¡ ¢¢ 1 − p p  = exp − n f r ,  ¡ ¢ r r n p+ n 1− p+ n where3 ´ ¡ ´ ¢ ³ ¡ ¢ ³ f (x) = p + x ln 1 + px + 1 − (p + x) ln 1 − 1−x p . Below we will show that f (x) ≥ 2x2 for all x ∈ R such that f (x) ∈ R, so that (9.5) becomes h i ¡ ¡ ¢¢ Pr Y ≥ E [Y ] + r ≤ exp − n f nr ³ ¡ ¢2 ´ ≤ exp −2n nr ³ ´ 2 = exp − 2rn . This will complete the proof. All that remains is to show that f (x) ≥ 2x2 for all x such that f (x) ∈ R—namely, for − p < x < 1 − p, though we will only need the range 0 ≤ x < 1 − p.4 This can be shown by calculus: the first and second derivatives of f are ³ ´ ³ ´ f 0 (x) = ln 1 + px − ln 1 − 1−x p , f 00 (x) = 1 . (1 − (p + x))(p + x) In particular, f 00 (x) is minimized when p + x = 12 , at which point f 00 (x) = 4. Thus, the fundamental theorem of calculus gives Z x Z x f 0 (x) = f 0 (0) + f 00 (t) dt ≥ 4 dt = 4x. | {z } t=0 t=0 0 Applying the fundamental theorem of calculus again, we have Z x Z x f (x) = f (0) + f 0 (t) dt ≥ 4t dt = 2x2 . |{z} t=0 t=0 0 3 The definition of f may seem unmotivated here, but in fact f (x) is properly interpreted as the relative entropy between two Bernoulli random variables with parameters p and p + x, respectively. Relative entropy is a measure of the “distance” between two probability distributions. 4 Note that x = r will always fall within this range, as we must have E [Y ] + r ≤ n. (Or at least, the theorem becomes n trivial when nr > 1 − p.) Lec 9 – pg. 5 of 9 ai pivot Figure 9.3. In a given iteration of Q UICKSORT, there will be several working subarrays, each in the process of being sorted by its own recursive call to Q UICKSORT. 9.2 Analysis of Q UICKSORT Recall the procedure Q UICKSORT, which sorts an array A = 〈a 1 , . . . , a n 〉 in place (see Figure 9.3): Algorithm: Q UICKSORT(A) 1. Choose an element x ∈ A uniformly at random. We will call x the “pivot.” 2. Partition A around x. 3. Sort the elements less than x recursively. 4. Sort the elements greater than x recursively. We saw in recitation that the expected running time of Q UICKSORT is Θ(n lg n). In this lecture we’ll use the Chernoff bound to show that, for some constant c ≥ 1, the probability that Q UICKSORT takes more than cn lg n time on any given input is at most n1 . In fact, what we’ll show is that after time cn lg n, the probability that the working subarray containing any given element a ∈ A consists of more than one element is at most n12 . Once this is established, the union bound shows that the probability that there exists any working subarray with more than one element is at most n1 . That is to say, let A = 〈a 1 , . . . , a n 〉 and let E i be the event that after time cn lg n, the working subarray containing a i has more than one element. Then the union bound states that " # · ¸ µ ¶ n n X [ £ ¤ 1 1 ∃ working subarray with Pr E i ≤ n 2 = . Pr = Pr Ei ≤ more than one element n n i =1 i =1 (In general, the union bound says that the probability of a finite or countably infinite union of events E i is at most the sum of their individual probabilities. The intuition is that equality is achieved when the E i ’s are pairwise disjoint, and any overlap only diminishes the size of the union.) All that remains is to find c such that, for any array A, £ ¤ 1 Pr E i ≤ 2 n for all i = 1, . . . , n. As in Lecture 8, we define a “good” pivot x in an array A to be a pivot such that 1 9 | | | | 10 A ≤ rank(x) ≤ 10 A . 9 as big. Let X i,k be the Thus, a good pivot splits the current array into two subarrays each at most 10 indicator random variable ( 0 if, in the kth iteration, a good pivot was chosen for a i ’s subarray X i,k = 1 otherwise. Lec 9 – pg. 6 of 9 (By “the kth iteration,” we mean all calls to Q UICKSORT at recursive depth k. Thus, the kth iteration will consist of 2k−1 recursive calls to Q UICKSORT, assuming none of the subarrays have shrunk to size 1 yet.) Note two things: £ ¤ • E X i,k = 0.2 for all i and all k. (To reduce the amount of bookkeeping we have to do, we will assume that pivots continue to be chosen even after an element’s subarray is reduced to size 1, and that the probability of choosing a good pivot continues to be 0.8.) • For a fixed k, the variables X 1,k , X 2,k , . . . , X n,k are dependent on each other. However, for a fixed i, the variables X i,1 , X i,2 , . . . are independent of each other. For a fixed i and a fixed K, we have " E K X # X i,k = 0.2K. k=1 Thus, by the Chernoff bound (with r = 0.1K), we have " # ¶ µ K X 2(0.1K)2 X i,k > 0.2K + 0.1K ≤ exp − Pr = exp (−0.02K) . K k=1 Now let K = 100 ln n. We obtain " Pr K X # X i,k > 0.3K ≤ k=1 1 . n2 PK On the other hand, if k=1 X i,k ≤ 0.3K, then at least 0.7K of the first K pivots were good, and the size of the working subarray containing a i after K steps is at most µ ¶0.7K µ ¶70 ln n 9 9 n· = n· = n70 ln(9/10)+1 ≈ n−6.3 < 1 10 10 (i.e., the size is at most 1; the reason for the fractional number is that we are ignoring issues of rounding). Thus, after K = 100 ln n iterations, the probability that the working subarray containing a i has more than one element is at most n12 . So by the union bound, the probability that Q UICKSORT requires more than K iterations is at most n1 . While the sizes of the inputs to each iteration and the total number of iterations required are random, the running time of the non-recursive part of Q UICKSORT is deterministic: It takes Θ(A) time to pick a random element and partition around that element. Let’s say it takes at most τ A time to do this, where τ is some appropriately chosen constant. Now, if the sizes of the inputs to the kth P iteration are m 1 , . . . , m ` , then the quantities m 1 , . . . , m ` are random, but we know `λ=1 m λ = n, so the P` total amount of time required by the kth iteration is at most λ=1 τ m λ = τ n. Thus, the probability that Q UICKSORT takes more than K τ n = (100τ)n ln n time is at most 1/n. This is what we set out to show in the beginning of this section, with c = 100τ. To recap: How can we argue about randomized algorithms? • Identify the random choices in the algorithm. • After fixing the random choices, we have a deterministic algorithm. In this example, the ¯random choices were the pivots. Fixing the sequence of choices of pivots, we ¯ ¯ ¯ were able to analyze A i,k , the size of the subarray containing a i after k iterations, for each i and k (see Figure 9.4). Lec 9 – pg. 7 of 9 Random choices at depth 1 Random choices at depth 2 .. . ¯ ¯ ¯ A 1,1 ¯ = n ¯ ¯ ¯ A 1,2 ¯ = 0.3n .. . ¯ ¯ ¯ A 2,1 ¯ = n ¯ ¯ ¯ A 2,2 ¯ = 0.8n .. . ··· ··· .. . Figure 9.4. The values 0.3n and 0.8n are just examples, and of course depend on the sequence of random choices. Once the sequence of random choices is fixed, we would like to know how many rows down we must go before all entries are 1. 9.3 Monte Carlo Sampling Suppose that out of a large population U, there occurs a certain phenomenon in a subset S ⊆ U. S| Given an element x, we are able to test whether x ∈ S. How can we efficiently estimate ||U | ? For example, how can we efficiently estimate what fraction of the world’s population is left-handed, or what percentage of voters vote Republican? There is an elegant simple solution to this problem: Choose a k-element¯ sample A = { x1 , . . . , xk } ⊆ © ª¯ S| ¯ b | A ∩S | 1 ¯ U uniformly at random. We then estimate ||U | by the quantity S = | A | = k i : x i ∈ S , figuring that the chance that an element a ∈ A belongs to S ought to be the same as the chance that a general element x ∈ U belongs to S. Thus, we are relying heavily on our ability to pick a truly uniform 5 b sample. ³ ´ Assuming this reliance is safe, k S = | A ∩ S | is a binomial random variable with parameters |S | S| k, |U | . In particular, the expected value of Sb is the exact correct answer ||U | . Thus, the Chernoff bound states that for any r > 0, · ¸ h i £ ¤ ¡ ¢ |S | Pr Sb ≥ + r = Pr k Sb ≥ E k Sb + kr ≤ exp −2kr 2 . |U | i h S| Exercise 9.1. How can we use the Chernoff bound to give an upper bound on Pr Sb ≤ ||U − r ? (Hint: | replace S by its complement U \ S.) 9.4 Amplification Suppose we are given a Monte Carlo algorithm which always runs in time T and returns the correct answer with probability 2/3. (Assume there is a unique correct answer.) Then, for any ² > 0, we can ¡ ¢ create a new randomized algorithm which always runs in time O T lg 1² and outputs an incorrect answer with probability at most ². How? ¡ ¢ The plan is to run the original algorithm k times, where k = O lg 1² is a quantity which we will determine later. The algorithm should then output whichever answer occurred most frequently out of the k computed answers. To bound the probability of error, let I j be the indicator random variable P which equals 1 if the jth run returns an incorrect answer, and let I = kj=1 I j . Then I is a binomial ¡ 1¢ random variable with parameters k, 3 . Thus, by the Chernoff bound, Pr · ¸ h i £ ¤ ¡ 1 ¢ we ultimately return ≤ Pr I ≥ 12 k = Pr I ≥ E [I] + 61 k ≤ exp − 18 k . an incorrect answer 5 In practice, it could be quite hard to pick a uniform sample. For example, what if you wanted figure out what proportion of New Yorkers speak Chinese? How much of your random sampling should be done in Chinatown? Without the help of extensive census data, it can be hard to make unbiased choices. Lec 9 – pg. 8 of 9 Thus, the probability of error will be at most ² if we let k = 18 ln 1² . Exercise 9.2. Suppose that instead of returning the correct answer with probability 2/3, our Monte Carlo algorithm returned the correct answer with probability p. What conditions on p allow the above strategy to work? In terms of p and ², how many times must we run the Monte Carlo algorithm? Lec 9 – pg. 9 of 9