Multi-Page Printing

6 1. BASICS ON LARGE DEVIATIONS variables deviate away from their equilibrium state, or on the event that the random variables take large values. In the following we consider a historically important example. Let {Xk}k≥1 be a real independent and identically distributed (i.i.d.) sequence such that there is a c 0 such that (1.1.8) E exp c|X1| ∞. If we take Yn to be the sample average (1.1.9) Xn = 1 n X1 + · · · + Xn n = 1, 2 · · · bn = n, then Assumption 1.1.1 holds with Λ(θ) = log E exp θX1 . Unfortunately, Λ(θ) is not essentially smooth in general. Indeed, it is straightfor- ward to check that Λ(θ) fails to be steep as X1 is bounded. Nevertheless, the large deviation principle known as the Cram´ er’s large deviation principle (Theorem 2.3.6, p. 44, [47]) claims that (1.1.4) and (1.1.5) (with bn = n) hold under (1.1.8). Further, log E exp θX1 ≥ θEX1 using Jensen inequality. Hence, Λ∗(EX1) = 0. On the other hand, assume that λ ∈ R satisfies Λ∗(λ) = 0. We have that λθ ≤ log E exp θX1 θ ∈ R. In view of the fact that lim θ→0 θ−1 log E exp θX1 = EX1, letting θ → 0+ and letting θ → 0− give, respectively, λ ≤ EX1 and λ ≥ EX1. Summarizing our argument, Λ∗(λ) = 0 if and only if λ = EX1. By the goodness of the rate function Λ∗(·), therefore, for given 0, inf |λ−EX1|≥ Λ∗(λ) 0. This observation shows that the probability that the sample average deviates away from the sample average EX1 has a genuine exponential decay. We summarize our discussion in the following theorem (Cram´ er’s large deviation principle). Theorem 1.1.5. Under the assumptions (1.1.8), lim sup n→∞ 1 n log P{Xn ∈ F } ≤ − inf x∈F Λ∗(x), lim inf n→∞ 1 n log P{Xn ∈ G} ≥ − inf x∈G Λ∗(x) for any closed set F ⊂ R and any open set G ⊂ R. In particular, for any 0, lim sup n→∞ 1 n log P |Xn − EX1| ≥ 0. For the inverse of the G¨ artner-Ellis theorem, we state the following Varadhan’s integral lemma.