Large Deviations for i.i.d. Random Variables

Advanced Stochastic Processes. LECTURE 3 Large Deviations for i.i.d. Random Variables Outline of Lecture • Chernoff bound using exponential moment generating functions. Examples. Legendre transforms. 3.1. Preliminary notes The Weak Law of Large Numbers tells us that if X1 , X2 , . . . , is an i.i.d. sequence of random variables with mean µ � E[X1 ] < ∞ then for every � > 0 P(| X1 + . . . + X n − µ| > �) → 0, n as n → ∞. But how quickly does this convergence to zero occur? We can try to use Chebyshev inequality which says P(| Var(X1 ) X1 + . . . + Xn − µ| > �) ≤ . n�2 n This suggest a ”decay rate” of order rate? Far from so ... 1 n if we treat Var(X1 ) and � as a constant. Is this an accurate 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 (we skip the proof). 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 large deviations rate. 1 2 3.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 > µ. We consider probability that the average of X1 , . . . , Xn exceeds a. The WLLN tells us that this happens with probability 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 n Xi > a) = P( � Xi > na) 1≤i≤n P θ 1≤i≤n Xi = P(e ≤ E[eθ P 1≤i≤n Xi > eθna ) ] eθna Markov inequality E[eθX1 · · · eθXn ] , = (eθa )n But recall that Xi ’s are i.i.d. Therefore E[eθX1 · · · eθXn ] = (E[eθX1 ])n . Thus we obtain an upper bound � E[eθX1 ] 1≤i≤n Xi P( > a) ≤ ( θa )n . n e Of course this bound is meaningful only if the ratio E[eθX1 ]/eθa is less than unity. At least we need E[eθX1 ] to be 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. Can we expect to find θ for which this is indeed the case? First assume for a moment that E[eθX1 ] is finite for all θ in some interval [0, θ0 ). Note that when θ = 0 the ratio E[eθX1 ]/eθa is equal to unity. Now let us differentiate this ratio with respect to θ at θ = 0: d E[eθX1 ] E[X1 eθX1 ]eθa − aeθa E[eθX1 ] = dθ eθa e2θa When we set θ = 0 we obtain that the derivative is E[X1 ] − a = µ − a < 0. Therefore, for sufficiently small θ the ratio E[eθX1 ]/eθa is indeed smaller than unity! We have established an upper bound part of the large deviations theory: Theorem 3.1 (Chernoff bound). Given an i.i.d. sequence X1 , . . . , Xn suppose E[eθX1 ] is finite for all θ in some interval [0, θ0 ). Let a > µ = E[X1 ]. Then for some sufficiently small θ > 0 there holds E[eθX1 ]/eθa < 1 and, moreover � E[eθX1 ] 1≤i≤n Xi P( > a) ≤ ( θa )n . n e In words the large deviations probability is exponentially (geometrically) small. How small can we make this ratio? We have some freedom in choosing θ as long as E[eθX1 ] is finite. So we could try to find θ which minimizes the ratio E[eθX1 ]/eθa . This is what we will do LECTURE 3. LARGE DEVIATIONS 3 in the rest of the lecture. The surprising conclusion of the large deviations theory is that such a minimizing value θ∗ exists and is tight. Namely it provides the correct decay rate! 3.3. Exponential moment generating function Definition 3.2. An exponential moment generating function of a random variable X with pa­ �∞ rameter θ is defined to be M (θ) � E[eθX ] = −∞ eθx dF (x). We will be primarily interested in the case when θ ≥ 0. Note that when θ = �0, we have M (0) = 0 1. Also when θ ≥ 0 the part of the integral corresponding to negative values −∞ eθx dF (x) is at most unity. Indeed since eθx ≤ 1 when x < 0 then � 0 � 0 θx e dF (x) ≤ dF (x) −∞ −∞ � ∞ ≤ dF (x) −∞ =1 However, the positive part �∞ 0 eθx dF (x) can be infinite (we will have examples later). The important case for us is when it is finite at least for some θ > 0. Proposition 1. Suppose M (θ) < ∞ for some θ > 0. Then for every 0 ≤ θ� < θ, also M (θ� ) < ∞. Thus the set of all θ for which M (θ) is finite is some interval. This interval can be open [0, θ0 ) or closed [0, θ0 ]. �0 � Proof. We showed already that −∞ eθ x dF (x) < ∞. Now consider an integral over the positive part: � ∞ � ∞ θ� x e dF (x) ≤ eθx dF (x) 0 �0 ∞ ≤ eθx dF (x) −∞ = M (θ) < ∞. �∞ � Therefore the entire integral M (θ� ) = −∞ eθ x dF (x) is finite. Thus the set of θ for which M (θ) is finite is an interval. We will show later that this interval is open from the right when the underlying distribution is exponential. Exercise 1 below asks you to find an example of a distribution for which the corresponding interval is closed. � Exercise 1. (a) Construct example of a random variable for which the corresponding inter­ val is trivial {0}. Namely, M (θ) = ∞ for every θ > 0. (b) (*) Construct an example of a random variable X for which the corresponding interval [0, θ0 ] is closed. That is M (θ0 ) < ∞, but M (θ� ) = ∞ for all θ� > θ0 . 4 3.4. Examples Let us do some examples of computing exponential moment generating functions. • Exponential distribution. Consider an exponentially distributed random variable X with parameter λ. Then � ∞ eθx λe−λx dx M (θ) = 0 � ∞ =λ e−(λ−θ)x dx. 0 �∞ −1 −(λ−θ)x � When θ < λ this integral is equal to λ−θ e � = 1/(λ − θ). But when θ ≥ λ, the 0 integral is infinite. Thus the exp. moment generating function is finite iff θ < λ and is M (θ) = λ/(λ − θ). In this case θ0 = λ and the corresponding interval [0, θ0 ) is open. Standard Normal distribution. When X has standard Normal distribution, we obtain � ∞ x2 1 θX M (θ) = E[e ] = √ eθx e− 2 dx 2π −∞ � ∞ x2 −2θx+θ 2 −θ 2 1 2 =√ e− dx 2π −∞ � ∞ (x−θ)2 θ2 1 =e2 √ e− 2 dx 2π −∞ Introducing change of variables y = x − θ we obtain that the integral is equal to � ∞ − y2 √1 e 2 dy = 1 (integral of the density of the standard Normal distribution). There2π −∞ θ2 fore M (θ) = e 2 . We see that it is always finite. That is θ0 = ∞. In a retrospect it is not surprising that in this case M (θ) is finite for all θ. The density 2 of the standard Normal distribution ”decays like” ≈ e−x and 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 parameter λ. Then ∞ � λm θX M (θ) = E[e ] = eθm e−λ m! m=0 = ∞ � (eθ λ)m −λ e m! m=0 = ee � θ λ−λ , m (where we use the formula m≥0 tm! = et ). Thus again the exp. moment generating function M (θ) is finite always. 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 . Exercise 2. θ ≥ 0. (a) Let X have a uniform distribution on an interval [0, 1]. Find M (θ) for all LECTURE 3. LARGE DEVIATIONS 5 (b) Suppose X is a bounded random variable. Namely a ≤ X ≤ b for some finite constants a < b. Prove that M (θ) is finite for all θ. 3.5. Legendre transforms Theorem 3.4 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 3.3. A Legendre transform of a random variable X is the function l(a) � supθ (θa − log M (θ)). (a) l(a) is a convex function of a. Proposition 2. (b) Suppose a > µ. Then l(a) = supθ≥0 (θa − log M (θ)) (no need to consider negative θ). (c) Consider θ0 – the largest θ for which M (θ) < ∞. There exists 0 < θ∗ < θ0 at which value l(a) is achieved: l(a) = aθ∗ − log M (θ∗ ). (a) Note that, for every fixed θ, the function θa − log M (θ), as a function of a is linear. Therefore l(a) is a supremum of linear functions. As such it is convex. (b) Since eθz is a convex function then using Jensen’s inequality M (θ) = E[eθX1 ] ≥ eθE[X1 ] = eθµ . When θ < 0 we have eθµ ≥ eθa , implying log M (θ) ≥ θa or aθ − log M (θ) < 0. But when θ = 0 this difference is 0 − M (0) = 0. So, indeed, there is no reason to consider negative θ when computing l(a). (c) This part is more difficult and technical. We skip the proof. � Proof. Armed with the results of this proposition, we can restate Theorem 3.4 in terms of θ∗ : Theorem 3.4 (Chernoff bound). Given an i.i.d. sequence X1 , . . . , Xn suppose E[eθX1 ] is finite for all θ in some interval [0, θ0 ). Let a > µ = E[X1 ]. Then � ∗ E[eθ X1 ] n 1≤i≤n Xi P( > a) ≤ ( θ∗ a ) n e −l(a)n , =e where θ∗ solves aθ∗ − log M (θ∗ ) = supθ (aθ − log M (θ)). 3.6. Additional reading materials • Course packet. Section 1.1 and Section 1.2 up to including page 15. • Chapter 0 of [1]. This is non-technical introduction to the field which describes motiva­ tion and various applications of the large deviations theory. Soft reading.