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.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2010 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.