18.310 Lecture Notes: Chernoff Bounds, and Some Applications

18.310 lecture notes June 3, 2014 Chernoff bounds, and some applications 1 Preliminaries Before we venture into Chernoff bound, let us recall two simple bounds on the probability that a random variable deviates from the mean by a certain amount: Markov’s inequality and Chebyshev’s inequality. Markov’s inequality only applies to non-negative random variables and gives us a bound depending on the expectation of the random variable. Theorem 1 (Markov’s Inequality). Let X : S → R be a non-negative random variable. Then, for any a > 0, P(X ≥ a) ≤ E(X) . a Proof. Let A denote the event {X ≥ a}. Then: E(X) = P(ω)X(ω) = ω∈S As X is non-negative, we have ω∈Ā P(ω)X(ω) + ω∈A P(ω)X(ω). ω∈Ā P(ω)X(ω) ≥ 0. Hence: E(X) ≥ P(ω)X(ω) ≥ a ω∈A P(ω) = a · P(A). ω∈A Chebyshev’s inequality requires the variance of the random variable and is normally stronger. Theorem 2 (Chebyshev’s Inequality). Let X : S → R be a random variable with expectation E(X) and variance Var(X). Then, for any a ∈ R: P(|X − E(X)| ≥ a) ≤ Var(X) . a2 Proof. Apply Markov’s Inequality to the non-negative random variable (X − E(X))2 . Notice that E (X − E(X))2 = Var(X). Even though Markov’s and Chebyshev’s Inequality only use information about the expectation and the variance of the random variable under consideration, they are essentially tight for a general random variable. Exercise Verify this by constructing non-trivial (i.e. non-constant) random variables for which Theo­ rem 1 and Theorem 2 are tight, i.e. hold with equality. Chernoff-1 2 Deviation of a sum on independent random variables As we are not able to improve Markov’s Inequality and Chebyshev’s Inequality in general, it is worth to consider whether we can say something stronger for a more restricted, yet interesting, class of random variables. This idea brings us to consider the case of a random variable that is the sum of a number of independent random variables. This scenario is particularly important and ubiquitous in statistical applications. Examples of such random variables are the number of heads in a sequence of coin tosses, or the average support obtained by a political candidate in a poll. Can Markov’s and Chebyshev’s Inequality be improved for this particular kind of random variable? Before confronting this question, let us check what Chebyshev’s Inequality (the stronger of the two) gives us for a sum of independent random variables. Theorem 3. Let X1 , X2 , . . . , Xn be independent random variables with E(Xi ) = µi and Var(Xi ) = σi2 . Then, for any a > 0: Pn n n X X σ2 P(| Xi − µi | ≥ a) ≤ i=12 i a i=1 i=1 Proof. This follows from Chebyshev’s Inequality applied to P n i=1 Var(Xi ) for independent variables. Pn i=1 Xi and the fact that Var( Pn i=1 Xi ) = In particular, for identically distributed random variables with expectation µ and variance σ 2 , we obtain � �� Pn � � i=1 Xi � σ2 � � − µ� ≥ b ≤ 2 P � n nb for any b > 0. We covered this derivation in the lecture on the Weak Law of Large Numbers. Can this result be improved or is it tight? At a first glance, you may suspect that this is tight, as we have made P use of all ourPassumptions. In particular, we exploited the independence of the variables {Xi } n n to get Var( i=1 Xi ) = i=1 Var(Xi ). Notice, however, that this last step actually only uses the pairwise independence of the variables {Xi }, i.e. the fact that, for all couples i 6= j ∈ [n] and all x, y ∈ R: P(Xi = x ∧ Xj = y) = P(Xi = x) · P(Xj = y). (1) Indeed, it is possible to show that Theorem 3 is tight when all the variables {Xi } are just guaranteed to be pairwise independent. Hard Exercise Let X1 , . . . , Xd be independent random variables that take value 1 or −1, each with probability 1/2. For each S ⊆ [d], definePthe random variable YS = i∈S Xi . i) Show that the variables {YS } are pairwise independent. ii) Let Z = S⊆D YS . Show that Chebyshev’s Inequality is asymptotically tight for Z. We are now ready to tackle the case of a sum of independent random variables. Recall that we are now using the following strong version of independence (also known as joint or mutual independence), which guarantees the same property of Equation 1 for any subset S ⊆ [n] of random variables: � � ∀S ⊆ [n], P( Xi = xi ) = P(Xi = xi ). i∈S i∈S In this case, the proof of Theorem 3 is too weak as it does not rely on the joint independence. In the next section, we will see that we can indeed obtain stronger bounds under this stronger assumpiton. These bounds are known as Chernoff bounds, after Herman Chernoff, Emeritus Professor of Applied Mathematics here at MIT! Chernoff-2 3 Chernoff Bound There are many different forms of Chernoff bounds, each tuned to slightly different assumptions. We will start with the statement of the bound for the simple case of a sum of independent Bernoulli trials, i.e. the case in which each random variable only takes the values 0 or 1. For example, this corresponds to the case of tossing unfair coins, each with its own probability of heads, and counting the total number of heads. Pn Theorem 4 (Chernoff Bounds). Let X = i=1 Xi , where XiP= 1 with probability pi and Xi = 0 with n probability 1 − pi , and all Xi are independent. Let µ = E(X) = i=1 pi . Then δ2 (i) Upper Tail: P(X ≥ (1 + δ)µ) ≤ e− 2+δ µ for all δ > 0; (ii) Lower Tail: P(X ≤ (1 − δ)µ) ≤ e−µδ 2 /2 for all 0 < δ < 1; Notice that the lower and upper tail take slightly different forms. Curiously, this is necessary and boils down to the use of different approximation of the logarithmic function. There exist more general versions of this bound, where this asymmetry is not present, but they are more complicated, as the involve the entropy of the distribution at the exponent. 3.1 Proof idea and moment generating function Let X be any random variable, and a ∈ R. We will make use of the same idea which we used to prove Chebyshev’s inequality from Markov’s inequality. For any s > 0, P(X ≥ a) = P(esX ≥ esa ) ≤ E(esX ) esa by Markov’s inequality. (2) (Recall that to obtain Chebyshev, we squared both sides in the first step, here we exponentiate.) So we have some upper bound on P(X > a) in terms of E(esX ). Similarly, for any s > 0, we have P(X ≤ a) = P(e−sX ≥ e−sa ) ≤ E(e−sX ) e−sa The key player in this reasoning is the moment generating function MX of the random variable X, which is a function from R to R defined by MX (s) = E esX . The reason for the name is related to the Taylor expansion of esX ; assuming it converges, we have MX (s) = E 1 + sX + 21 s2 X 2 + 1 3 3 3! s X + ··· = ∞ X 1 i s E(X i ). i! i=0 The terms E(X i ) are called “moments” and encode important information about the distribution; notice that the first moment (i = 1) is just the expectation, and the second moment is closely related to the variance. So the moment generating function encodes information of all of these moments in some way. Moment generating functions behave wonderfully with respect to addition of independent random vari­ ables: Pn Lemma 1. If X = i=1 Xi where X1 , X2 , . . . , Xn are independent random variables, then MX (s) = n � Y MXi (s). i=1 Chernoff-3 Proof. � MX (s) = E(esX ) = E es � n � � Y sXi =E e n i=1 Xi � i=1 = = n � Y i=1 n � Y E(esXi ) by independence MXi (s). i=1 This lemma allows us to prove a Chernoff bound by bounding the moment generating function of each Xi individually. 3.2 Proof of Theorem 4 Before proceeding to prove the theorem, we compute the form of the moment generating function for a single Bernoulli trial. Our goal is to then combine this expression with Lemma 1 in the proof of Theorem 4. Lemma 2. Let Y be a random variable that takes value 1 with probability p and value 0 with probability 1 − p. Then, for all s ∈ R: s MY (s) = E(esY ) ≤ ep(e −1) . Proof. We have: MY (s) = E(esY ) = p · es + (1 − p) · 1 by definition of expectation s = 1 + p(e − 1) ≤ ep(e s −1) using 1 + y ≤ ey with y = p(es − 1). We are now ready to prove Theorem 4 by combining Lemma 1 and 2. Proof of Theorem 4. Applying Lemma 1 and Lemma 2, we obtain MX (s) ≤ n Y � epi (e s −1) = e(e s −1) n i=1 pi ≤ e(e s −1)µ , (3) i=1 Pn using that i=1 pi = E(X) = µ. For the proof of the upper tail, we can now apply the strategy described in Equation 2, with a = (1 + δ)µ and s = ln(1 + δ). s P(X ≥ (1 + δ)µ) ≤ e−s(1+δ)µ e(e −1)µ)  � µ � eδ = . (1 + δ)1+δ Chernoff-4 Our choice of s is motivated as follows: we are trying to make our upper bound for the tail probability to be as small as possible. To do this, we can minimize our expression for the upper bound as a function of s. Taking the derivative of the exponent shows that this minimum is achieved exactly at s = log(1 + δ). Taking the natural logarithm of the right-hand side yields µ(δ − (1 + δ) ln(1 + δ)). Using the following inequality for x > 0(left as an exercise): ln(1 + x) ≥ x , 1 + x/2 we obtain µ(δ − (1 + δ) ln(1 + δ)) ≤ − δ2 µ. 2+δ Hence, we have the desired bound for the upper tail: �  � µ δ2 eδ P(X ≥ (1 + δ)µ) ≤ ≤ e− 2+δ µ . 1+δ (1 + δ) The proof of the lower tail is entirely analogous. It proceeds by taking s = ln(1 − δ) and applies the following inequality for the logarithm of (1 − δ) in the range 0 < δ < 1 : δ2 . 2 ln(1 − δ) ≥ −δ + Details are left as an exercise. 4 Other versions of Chernoff Bound For δ ∈ (0, 1), we can combine the lower and upper tails in Theorem 4 to obtain the following simple and useful bound: Corollary 5. With X and X1 , . . . , Xn as before, and µ = E(X), P(|X − µ| ≥ δµ) ≤ 2e−µδ 2 /3 for all 0 < δ < 1. Chernoff bound can be applied to more general settings than that of Bernoulli variables. In particular, the following version of the bound applies to bounded random variables, regardless of their distribution! Pn Theorem 6. Let X1 , X2 , . . . , Xn be random variables such that a ≤ Xi ≤ b for all i. Let X = i=1 Xi and set µ = E(X). Then, for all δ > 0 : 2 2 2δ µ − n(b−a) 2 (i) Upper Tail: P(X ≥ (1 + δ)µ) ≤ e ; 2 2 δ µ − n(b−a) 2 (ii) Lower Tail: P(X ≤ (1 − δ)µ) ≤ e . Example application: coin tossing Suppose we have a fair coin. Repeatedly toss the coin, and let Sn be the number of heads from the first n tosses. Then the weak law of large numbers tells us that P(|Sn /n − 1/2| ≥ E) → 0 as n → ∞. But what can we say about this probability for some fixed n? If we go back to the proof of the weak law that we gave in terms of Chebyshev’s inequality, we find that it tells us that P(|Sn /n − 1/2| ≥ E) ≤ Chernoff-5 1 . 4nE2 So for example, P(|Sn /n − 1/2| ≥ 1/4) ≤ n4 . But we can apply Chernoff instead of Chebyshev; what do we get then? From Corollary 5, using E(Sn ) = n/2, 2 P(|Sn − n/2| ≥ δ(n/2)) ≤ 2e−nδ /6 . Taking δ = 1/2 we obtain P(|Sn /n − 1/2| ≥ 1/4) ≤ 2e−n/24 . This is a massive improvement over the Chebyshev bound! Let’s try this now with a much smaller δ: let δ = 6 ln n/n. Then we obtain P(|Sn /n − 1/2| ≥ If instead we take δ just twice as large, δ = 2 P(|Sn /n − 1/2| ≥ 1 2 1 6 ln n/n) ≤ 2e− ln n = 2 . n 6 ln n/n, 6 ln n/n) ≤ 2e−4 ln n = 2 Chernoff-6 1 . n4