Lecture 3: Cramér’s Theorem

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6.265/15.070J Lecture 3 Fall 2013 9/11/2013 Large deviations Theory. Cramér’s Theorem Content. 1. Cramér’s Theorem. 2. Rate function and properties. 3. Change of measure technique. 1 Cramér’s Theorem We have established in the previous lecture that under some assumptions on the Moment Generating Function (MGF) M (θ), an i.i.d. sequence of random variables Xi , 1 ≤;i ≤ n with mean µ satisfies P(Sn ≥ a) ≤ exp(−nI(a)), where Sn = n−1 1≤i≤n Xi , and I(a) £ supθ (θa − log M (θ)) is the Legendre transform. The function I(a) is also commonly called the rate function in the theory of Large Deviations. The bound implies lim sup n log P(Sn ≥ a) ≤ −I(a), n and we have indicated that the bound is tight. Namely, ideally we would like to establish the limit lim sup n log P(Sn ≥ a) = −I(a), n Furthermore, we might be interested in more complicated rare events, beyond the interval [a, ∞). For example, the likelihood that P(Sn ∈ A) for some set A ⊂ R not containing the mean value µ. The Large Deviations theory says that roughly speaking 1 P(Sn ∈ A) = − inf I(x), n→∞ n x∈A lim 1 (1) but unfortunately this statement is not precisely correct. Consider the following example. Let X be an integer-valued random variable, and A = { m p : m ∈ Z, p is odd prime.}. Then for prime n, we have P(Sn ∈ A) = 1; but for n = 2k , n ∈A) we have P (Sn ∈ A) = 0. As a result, the limit limn→∞ log P (S in this case n does not exist. The sense in which the identity (1) is given by the Cramér’s Theorem below. Theorem 1 (Cram´er’s Theorem). Given a sequence of i.i.d. real valued ran­ dom variables Xi , i ≥ 1 with a common moment generating function M (θ) = E[exp(θX1 )] the following holds: (a) For any closed set F ⊆ R, lim sup n→∞ 1 log P(Sn ∈ F ) ≤ − inf I(x), x∈F n (b) For any open set U ⊆ R, lim inf n→∞ 1 log P(Sn ∈ U ) ≥ − inf I(x). x∈U n We will prove the theorem only for the special case when D(M ) = R (namely, the MGF is finite everywhere) and when the support of X is entire R. Namely for every K > 0, P(X > K) > 0 and P(X < −K) > 0. For example a Gaussian random variable satisfies this property. To see the power of the theorem, let us apply it to the tail of Sn . In the following section we will establish that I(x) is a non-decreasing function on the interval [µ, ∞). Furthermore, we will establish that if it is finite in some interval containing x it is also continuous at x. Thus fix a and suppose I is finite in an interval containing a. Taking F to be the closed set [a, ∞) with a > µ, we obtain from the lim sup n→∞ 1 log P(Sn ∈ [a, ∞)) ≤ − min I(x) x≥a n = −I(a). Applying the second part of Cramér’s Theorem, we obtain lim inf n→∞ 1 1 log P(Sn ∈ [a, ∞)) ≤ lim inf log P(Sn ∈ (a, ∞)) n→∞ n n ≥ − inf I(x) x>a = −I(a). 2 Thus in this special case indeed the large deviations limit exists: 1 log P(Sn ≥ a) = −I(a). n→∞ n lim The limit is insensitive to whether the inequality is strict, in the sense that we also have 1 log P(Sn > a) = −I(a). n→∞ n lim 2 Properties of the rate function I Before we prove this theorem, we will need to establish several properties of I(x) and M (θ). Proposition 1. The rate function I satisfies the following properties (a) I is a convex non-negative function satisfying I(µ) = 0. Furthermore, it is an increasing function on [µ, ∞) and a decreasing function on (−∞, µ]. Finally I(x) = supθ≥0 (θx − log M (θ)) for every x ≥ µ and I(x) = supθ≤0 (θx − log M (θ)) for every x ≤ µ. (b) Suppose in addition that D(M ) = R and the support of X1 is R. Then, I is a finite continuous function on R. Furthermore, for every x ∈ R we have I(x) = θ0 x − log M (θ0 ), for some θ0 = θ0 (x) satisfying x= Ṁ (θ0 ) . M (θ0 ) (2) Proof of part (a). Convexity is due to the fact that I(x) is point-wise supremum. Precisely, consider λ ∈ (0, 1) I(λx + (1 − λ)y) = sup[θ(λx + (1 − x)y) − log M (θ)] θ = sup[λ(x − log M (θ)) + (1 − λ)(y − log M (θ))] ≤λ sup(x − log M (θ)) + (1 − λ) sup(y − log M (θ)) θ θ =λI(x) + (1 − λ)I(y). This establishes the convexity. Now since M (0) = 1 then I(x) ≥ 0 · x − log M (0) = 0 and the non-negativity is established. By Jensen’s inequality, we have that M (θ) = E[exp(θX1 )] ≥ exp(θE[X1 ]) = exp(θµ). 3 Therefore, log M (θ) ≥ θµ, namely, θµ − log M (θ) ≤ 0, implying I(µ) = 0 = minx∈R I(x). Furthermore, if x > µ, then for θ < 0 we have θx − log M (θ) ≤ θ(x − µ) < 0. This means that supθ (θx − log M (θ)) must be equal to supθ≥0 (θx − log M (θ)). Similarly we show that when x < µ, we have I(x) = supθ≤0 (θx − log M (θ)). Next, the monotonicity follows from convexity. Specifically, the existence of real numbers µ ≤ x < y such that I(x) > I(y) ≥ I(µ) = 0 violates convexity (check). This completes the proof of part (a). Proof of part (b). For any K > 0 we have lim inf θ→∞ log exp(θx) dP (x) log M (θ) = lim inf θ→∞ θ θ ∞ 1 ≥ lim inf log exp(θx) dP (x) θ→∞ θ K 1 ≥ lim inf log (exp(Kθ)P([K, ∞])) θ→∞ θ 1 = K + lim inf log P([K, ∞]) θ→∞ θ = K (since supp(X1 ) = R, we have P([K, ∞)) > 0.) Since K is arbitrary, lim inf θ→∞ 1 log M (θ) = ∞ θ Similarly, 1 lim inf − log M (θ) = ∞ θ→−∞ θ Therefore, lim θx − log M (θ) = lim θ(x − θ→∞ θ→∞ 1 log M (θ)) → −∞ θ Therefore, for each x as |θ| → ∞, we have that lim θx − log M (θ) = −∞ |θ|→∞ From the previous lecture we know that M (θ) is differentiable (hence continu­ ous). Therefore the supremum of θx − log M (θ) is achieved at some finite value θ0 = θ0 (x), namely, I(x) = θ0 x − log M (θ0 ) < ∞, 4 where θ0 is found by setting the derivative of θx − log M (θ) to zero. Namely, θ0 must satisfy (2). Since I is a finite convex function on R it is also continuous (verify this). This completes the proof of part (b). 3 Proof of Cramér’s Theorem Now we are equipped to proving the Cramér’s Theorem. Proof of Cramer’s ´ Theorem. Part (a). Fix a closed set F ⊂ R. Let α+ = min{x ∈ [µ, +∞) ∩ F } and α− = max{x ∈ (−∞, µ] ∩ F }. Note that α+ and α− exist since F is closed. If α+ = µ then I(µ) = 0 = minx∈R I(x). Note that log P(Sn ∈ F ) ≤ 0, and the statement (a) follows trivially. Similarly, if α− = µ, we also have statement (a). Thus, assume α− < µ < α+ . Then P (Sn ∈ F ) ≤ P (Sn ∈ [α+ , ∞)) + P (Sn ∈ (−∞, α− ]) Define xn £ P (Sn ∈ [α+ , ∞)) , yn £ P (Sn ∈ (−∞, α− ]) . We already showed that P (Sn ≥ α+ ) ≤ exp(−n(θα+ − log M (θ))), ∀θ ≥ 0. from which we have 1 log P (Sn ≥ α+ ) ≤ − (θα+ − log M (θ)), ∀θ ≥ 0. n 1 ⇒ log P (Sn ≥ α+ ) ≤ − sup(θα+ − log M (θ)) = −I(α+ ) n θ≥0 The second equality in the last equation is due to the fact that the supremum in I(x) is achieved at θ ≥ 0, which was established as a part of Proposition 1. Thus, we have lim sup n 1 log P (Sn ≥ α+ ) ≤ −I(α+ ) n (3) 1 log P (Sn ≤ α− ) ≤ −I(α− ) n (4) Similarly, we have lim sup n Applying Proposition 1 we have I(α+ ) = minx≥α+ I(x) and I(α− ) = minx≤α− I(x). Thus min{I(α+ ), I(α− )} = inf I(x) x∈F 5 (5) From (3)-(5), we have that 1 1 lim sup log xn ≤ − inf I(x), lim sup log yn ≤ − inf I(x), x∈F x∈F n n n n (6) which implies that lim sup n 1 log(xn + yn ) ≤ − inf I(x). x∈F n (you are asked to establish the last implication as an exercise). We have estab­ lished 1 lim sup log P (Sn ∈ F ) ≤ − inf I(x) (7) x∈F n n Proof of the upper bound in statement (a) is complete. Proof of Cram´er’s Theorem. Part (b). Fix an open set U ⊂ R. Fix E > 0 and find y such that I(y) ≤ inf x∈U ((x). It is sufficient to show that lim inf n→∞ 1 P (Sn ∈ U ) ≥ −I(y), n (8) since it will imply 1 P (Sn ∈ U ) ≥ − inf I(x) + E, n→∞ n x∈U and since E > 0 was arbitrary, it will imply the result. Thus we now establish (8). Assume y > µ. The case y < µ is treated similarly. Find θ0 = θ0 (y) such that lim inf I(y) = θ0 y − log M (θ0 ). Such θ0 exists by Proposition 1. Since y > µ, then again by Proposition 1 we may assume θ0 ≥ 0. We will use the change-of-measure technique to obtain the cover bound. For this, consider a new random variable let Xθ0 be a random variable defined by Z z 1 exp(θ0 x) dP (x) P(Xθ0 ≤ z) = M (θ0 ) −∞ Now, E[Xθ0 ] = 1 M (θ0 ) Z ∞ x exp(θ0 x) dP (x) −∞ Ṁ (θ0 ) M (θ0 ) = y, = 6 where the second equality was established in the previous lecture, and the last equality follows by the choice of θ0 and Proposition 1. Since U is open we can find δ > 0 be small enough so that (y − δ, y + δ) ⊂ U . Thus, we have P(Sn ∈ U ) ≥ P(Sn ∈ (y − δ, y + δ)) Z = dP (x1 ) · · · dP (xn ) 1 |n xi −y|<δ Z = 1 |n M −1 (θ0 ) exp(θ0 xi )dP (xi ). xi )M n (θ0 ) exp(−θ0 xi −y|<δ i 1≤i≤n (9) Since θ0 is non-negative, we obtain a bound P(Sn ∈ (y − δ, y + δ)) n ≥ exp(−θ0 yn − θ0 nδ)M (θ0 ) Z 1 |n M −1 (θ0 ) exp(θ0 xi )dP (xi ) xi −y|<δ 1≤i≤n However, we recognize the integral ; on the right-hand side of the inequality −1 above as the that the average n 1≤i≤n Yi of n i.i.d. random variables Yi , 1 ≤ i ≤ n distributed according to the distribution of Xθ0 belongs to the interval (y − δ, y + δ). Recall, however that E[Yi ] = E[Xθ0 ] = y (this is how Xθ0 was designed). Thus by the Weak Law of Large Numbers, this probability converges to unity. As a result Z −1 M −1 (θ0 ) exp(θ0 xi )dP (xi ) = 0. lim n log n→∞ 1 |n xi −y|<δ 1≤i≤n We obtain lim inf n−1 log P(Sn ∈ U ) ≥ −θ0 y − θ0 δ + log M (θ0 ) n→∞ = −I(y) − θ0 δ. Recalling that θ0 depends on y only and sending δ to zero, we obtain (8). This completes the proof of part (b). 7