Lecture 2: Large Deviations Technique

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6.265/15.070J Lecture 2 Fall 2013 9/9/2013 Large Deviations for i.i.d. Random Variables Content. Chernoff bound using exponential moment generating functions. Properties of a moment generating functions. Legendre transforms. 1 Preliminary notes The Weak Law of Large Numbers tells us that if X1 , X2 , . . . , is an i.i.d. se­ quence of random variables with mean µ £ E[X1 ] < ∞ then for every E > 0 P(| X1 + . . . + Xn − µ| > E) → 0, n as n → ∞. But how quickly does this convergence to zero occur? We can try to use Cheby­ shev inequality which says P(| Var(X1 ) X1 + . . . + Xn − µ| > E) ≤ . n nE2 This suggest a ”decay rate” of order n1 if we treat Var(X1 ) and E as a constant. Is this an accurate rate? Far from so ... In fact if the higher moment of X1 was finite, for example, E[X12m ] < ∞, then using a similar bound, we could show that the decay rate is at least n1m (exercise). The goal of the large deviation theory is to show that in many interesting cases the decay rate is in fact exponential: e−cn . The exponent c > 0 is called the large deviations rate, and in many cases it can be computed explicitly or numerically. 1 2 Large deviations upper bound (Chernoff bound) Consider an i.i.d. sequence with a common probability distribution function F (x) = P(X ≤ x), x ∈ R. Fix a value a > µ, where µ is again an expectation corresponding to the distribution F . We consider probability that the average of X1 , . . . , Xn exceeds a. The WLLN tells us that this happens with probabil­ ity converging to zero as n increases, and now we obtain an estimate on this probability. Fix a positive parameter θ > 0. We have P( 1≤i≤n Xi n > a) = P( Xi > na) 1≤i≤n = P(eθ 1≤i≤n Xi E[eθ 1≤i≤n Xi ≤ > eθna ) ] Markov inequality eθna E[ i eθXi ] , = (eθa )n But recall that Xi ’s are i.i.d. Therefore E[ obtain an upper bound 1≤i≤n Xi P( n ie � > a) ≤ θXi ] = (E[eθX1 ])n . Thus we E[eθX1 ] eθa �n . (1) Of course this bound is meaningful only if the ratio E[eθX1 ]/eθa is less than unity. We recognize E[eθX1 ] as the moment generating function of X1 and de­ note it by M (θ). For the bound to be useful, we need E[eθX1 ] to be at least finite. If we could show that this ratio is less than unity, we would be done – exponentially fast decay of the probability would be established. Similarly, suppose we want to estimate P( 1≤i≤n Xi n < a), for some a < µ. Fixing now a negative θ < 0, we obtain P( 1≤i≤n Xi n < a) = P(eθ 1≤i≤n Xi > eθna ) � � M (θ) n ≤ , eθa 2 and now we need to find a negative θ such that M (θ) < eθa . In particular, we need to focus on θ for which the moment generating function is finite. For this purpose let D(M ) £ {θ : M (θ) < ∞}. Namely D(M ) is the set of values θ for which the moment generating function is finite. Thus we call D the domain of M . 3 Moment generating function. Examples and properties Let us consider some examples of computing the moment generating functions. • Exponential distribution. Consider an exponentially distributed random variable X with parameter λ. Then ∞ M (θ) = 0 eθx λe−λx dx ∞ =λ e−(λ−θ)x dx. 0 ∞ −1 −(λ−θ)x When θ < λ this integral is equal to λ−θ e = 1/(λ − θ). But 0 when θ ≥ λ, the integral is infinite. Thus the exp. moment generating function is finite iff θ < λ and is M (θ) = λ/(λ − θ). In this case the domain of the moment generating function is D(M ) = (−∞, λ). Standard Normal distribution. When X has standard Normal distribu­ tion, we obtain 1 M (θ) = E[eθX ] = √ 2π 1 =√ 2π =e θ2 2 ∞ −∞ ∞ eθx e− e− x2 2 dx x2 −2θx+θ 2 −θ 2 2 dx −∞ 1 √ 2π ∞ e− (x−θ)2 2 dx −∞ Introducing change of variables y = x − θ we obtain that the integral is equal to √1 2π 2 ∞ −y 2 −∞ e dy = 1 (integral of the density of the standard θ2 Normal distribution). Therefore M (θ) = e 2 . We see that it is always finite and D(M ) = R. In a retrospect it is not surprising that in this case M (θ) is finite for all θ. 2 The density of the standard Normal distribution ”decays like” ≈ e−x and 3 this is faster than just exponential growth ≈ eθx . So no matter how large is θ the overall product is finite. • Poisson distribution. Suppose X has a Poisson distribution with param­ eter λ. Then M (θ) = E[eθX ] = = ∞ X eθm m=0 θ (e λ)m −λ m! m=0 = ee ∞ X θ λ−λ λm −λ e m! e , P m (where we use the formula m≥0 tm! = et ). Thus again D(M ) = R. This again has to do with the fact that λm /m! decays at the rate similar to 1/m! which is faster then any exponential growth rate eθm . We now establish several properties of the moment generating functions. Proposition 1. The moment generating function M (θ) of a random variable X satisfies the following properties: (a) M (0) = 1. If M (θ) < ∞ for some θ > 0 then M (θ ' ) < ∞ for all θ' ∈ [0, θ]. Similarly, if M (θ) < ∞ for some θ < 0 then M (θ' ) < ∞ for all θ' ∈ [θ, 0]. In particular, the domain D(M ) is an interval containing zero. (b) Suppose (θ1 , θ2 ) ⊂ D(M ). Then M (θ) as a function of θ is differentiable in θ for every θ0 ∈ (θ1 , θ2 ), and furthermore, d M (θ) dθ θ=θ0 = E[Xeθ0 X ] < ∞. Namely, the order of differentiation and expectation operators can be changed. Proof. Part (a) is left as an exercise. We now establish part (b). Fix any θ0 ∈ (θ1 , θ2 ) and consider a θ-indexed sequence of random variables Yθ £ exp(θX) − exp(θ0 X) . θ − θ0 4 d Since dθ exp(θx) = x exp(θx), then almost surely Yθ → X exp(θ0 X), as θ → θ0 . Thus to establish the claim it suffices to show that convergence of expectations holds as well, namely limθ→θ0 E[Yθ ] = E[X exp(θ0 X)], and E[X exp(θ0 X)] < ∞. For this purpose we will use the Dominated Convergence Theorem. Namely, we will identify a random variable Z such that |Yθ | ≤ Z al­ most surely in some interval (θ0 − E, θ0 + E), and E[Z] < ∞. Fix E > 0 small enough so that (θ0 − E, θ0 + E) ⊂ (θ1 , θ2 ). Let Z = E−1 exp(θ0 X + E|X|). Using the Taylor expansion of exp(·) function, for every θ ∈ (θ0 − E, θ0 + E), we have �  �  1 1 1 Yθ = exp(θ0 X) X + (θ − θ0 )X 2 + (θ − θ0 )2 X 3 + · · · + (θ − θ0 )n−1 X n + · · · , 2! 3! n! which gives � �   1 1 |Yθ | ≤ exp(θ0 X) |X| + (θ − θ0 )|X|2 + · · · + (θ − θ0 )n−1 |X|n + · · · 2! n! � �   1 1 n−1 2 n ≤ exp(θ0 X) |X| + E|X| + · · · + E |X| + · · · 2! n! = exp(θ0 X)E−1 (exp(E|X|) − 1) ≤ exp(θ0 X)E−1 exp(E|X|) = Z. It remains to show that E[Z] < ∞. We have E[Z] = E−1 E[exp(θ0 X + EX)1{X ≥ 0}] + E−1 E[exp(θ0 X − EX)1{X < 0}] ≤ E−1 E[exp(θ0 X + EX)] + E−1 E[exp(θ0 X − EX)] = E−1 M (θ0 + E) + E−1 M (θ0 − E) < ∞, since E was chosen so that (θ0 − E, θ0 + E) ⊂ (θ1 , θ2 ) ⊂ D(M ). This completes the proof of the proposition. Problem 1. (a) Establish part (a) of Proposition 1. (b) Construct an example of a random variable for which the corresponding interval is trivial {0}. Namely, M (θ) = ∞ for every θ > 0. 5 (c) Construct an example of a random variable X such that D(M ) = [θ1 , θ2 ] for some θ1 < 0 < θ2 . Namely, the the domain D is a non-zero length closed interval containing zero. Now suppose the i.i.d. sequence Xi , i ≥ 1 is such that 0 ∈ (θ1 , θ2 ) ⊂ D(M ), where M is the moment generating function of X1 . Namely, M is finite in a neighborhood of 0. Let a > µ = E[X1 ]. Applying Proposition 1, let us differentiate this ratio with respect to θ at θ = 0: d M (θ) E[X1 eθX1 ]eθa − aeθa E[eθX1 ] = = µ − a < 0. dθ eθa e2θa Note that M (θ)/eθa = 1 when θ = 0. Therefore, for sufficiently small positive θ, the ratio M (θ)/eθa is smaller than unity, and (1) provides an exponential bound on the tail probability for the average of X1 , . . . , Xn . Similarly, if a < µ, the ratio M (θ)/eθa < 1 for sufficiently small negative θ. We now summarize our findings. Theorem 1 (Chernoff bound). Given an i.i.d. sequence X1 , . . . , Xn suppose the moment generating function M (θ) is finite in some interval (θ1 , θ2 ) : 0. Let a > µ = E[X1 ]. Then there exists θ > 0, such that M (θ)/eθa < 1 and P � �   M (θ) n 1≤i≤n Xi P( > a) ≤ . n eθa Similarly, if a < µ, then there exists θ < 0, such that M (θ)/eθa < 1 and P � �   M (θ) n 1≤i≤n Xi P( < a) ≤ . n eθa How small can we make the ratio M (θ)/ exp(θa)? We have some freedom in choosing θ as long as E[eθX1 ] is finite. So we could try to find θ which minimizes the ratio M (θ)/eθa . This is what we will do in the rest of the lecture. The surprising conclusion of the large deviations theory is very often that such a minimizing value θ∗ exists and is tight. Namely it provides the correct decay rate! In this case we will be able to say P 1≤i≤n Xi P( > a) ≈ exp(−I(a, θ∗ )n), n where I(a, θ∗ ) = − log M (θ∗ )/eθ ∗a . 6 4 Legendre transforms Theorem 1 gave us a large deviations bound (M (θ)/eθa )n which we rewrite as e−n(θa−log M (θ)) . We now study in more detail the exponent θa − log M (θ). Definition 1. A Legendre transform of a random variable X is the function I(a) £ supθ∈R (θa − log M (θ)). Let us go over the examples of some distributions and compute their corre­ sponding Legendre transforms. • Exponential distribution with parameter λ. Recall that M (θ) = λ/(λ− θ) when θ < λ and M (θ) = ∞ otherwise. Therefore when θ < λ I(a) = sup(aθ − log θ λ ) λ−θ = sup(aθ − log λ + log(λ − θ)), θ and I(a) = −∞ otherwise. Setting the derivative of g(θ) = aθ − log λ + log(λ − θ) equal to zero we obtain the equation a − 1/(λ − θ) = 0 which has the unique solution θ∗ = λ − 1/a. For the boundary cases, we have aθ − log λ + log(λ − θ)) → −∞ when either θ ↑ λ or θ → −∞ (check). Therefore I(a) = a(λ − 1/a) − log λ + log(λ − λ + 1/a) = aλ − 1 − log λ + log(1/a) = aλ − 1 − log λ − log a. The large deviations bound then tells us that when a > 1/λ P 1≤i≤n Xi P( > a) ≈ e−(aλ−1−log λ−log a)n . n Say λ = 1 and a = 1.2. Then the approximation gives us ≈ e−(.2−log 1.2)n . Note that we can obtain an exact expression for this tail probability. In­ deed, X1 , X1 + X2 , . . . , X1 + X2 · · · + Xn , . . . are the events of a Poisson process with parameter λ = 1. Therefore we can compute the probabil­ ity P( 1≤i≤n Xi > 1.2n) exactly: it is the probability that the Poisson 7 process has at most n − 1 events before time 1.2n. Thus P X 1≤i≤n Xi P( > 1.2) = P( Xi > 1.2n) n 1≤i≤n = X 0≤k≤n−1 (1.2n)k −1.2n e . k! It is not at all clear how revealing this expression is. In hindsight, we know that it is approximately e−(.2−log 1.2)n , obtained via large deviations theory. θ2 • Standard Normal distribution. Recall that M (θ) = e 2 when X1 has the standard Normal distribution. The expected value µ = 0. Thus we fix a > 0 and obtain I(a) = sup(aθ − = θ a2 2 θ2 ) 2 , achieved at θ∗ = a. Thus for a > 0, the large deviations theory predicts that P a2 1≤i≤n Xi P( > a) ≈ e− 2 n . n P Xi Again we could compute this probability directly. We know that 1≤i≤n n is distributed as a Normal random variable with mean zero and variance 1/n. Thus P √ Z ∞ t2 n n 1≤i≤n Xi P( > a) = √ e− 2 dt. n 2π a After a little bit of technical work one could R a+E show that this integral is ”dominated” by its part around a, namely, a ·, which is further approx­ √ a2 n − n imated by the value of the function itself at a, namely √2π e 2 . This is consistent with the value given√ by the large deviations theory. Simply the n lower order magnitude term √2π disappears in the approximation on the log scale. 8 • Poisson distribution. Suppose X has a Poisson distribution with param­ θ eter λ. Recall that in this case M (θ) = ee λ−λ . Then I(a) = sup(aθ − (eθ λ − λ)). θ Setting derivative to zero we obtain θ∗ = log(a/λ) and I(a) = a log(a/λ)− (a − λ). Thus for a > λ, the large deviations theory predicts that P 1≤i≤n Xi P( > a) ≈ e−(a log(a/λ)−a+λ)n . n In this case as well we can compute the large deviations probability ex­ plicitly. The sum X1 + · · · + Xn of Poisson random variables is also a Poisson random variable with parameter λn. Therefore P( X Xi > an) = 1≤i≤n X (λn)m e−λn . m! m>an But again it is hard to infer a more explicit rate of decay using this expres­ sion 5 Additional reading materials • Chapter 0 of [2]. This is non-technical introduction to the field which de­ scribes motivation and various applications of the large deviations theory. Soft reading. • Chapter 2.2 of [1]. References [1] A. Dembo and O. Zeitouni, Large deviations techniques and applications, Springer, 1998. [2] A. Shwartz and A. Weiss, Large deviations for performance analysis, Chap­ man and Hall, 1995. 9