the Gartner-Ellis theorem
/ GERT-ner EL-iss /
The Gartner-Ellis theorem is the extension of Cramer's theorem beyond independent identically distributed sums to dependent and otherwise general sequences. Cramer needs the iid structure to compute the log-mgf exactly as n times a single-variable cumulant; Gartner-Ellis replaces that with a single limiting object — the limiting scaled cumulant generating function — and asks only that it exist and behave nicely. This is what lets large deviations be applied to Markov chain additive functionals, sample means with weak dependence, and many statistical-mechanics quantities.
Let Z_n be random vectors in R^d and define the scaled cumulant generating function Lambda(theta) = lim (1/n) log E[e^(n <theta, Z_n>)], assuming the limit exists as an extended real number for every theta. If Lambda is finite in a neighbourhood of the origin and is essentially smooth and lower semicontinuous (the 'steepness' hypotheses), then Z_n satisfies an LDP with the good convex rate function I = Lambda*, the Legendre-Fenchel transform of Lambda. So the whole effect of dependence is absorbed into the single function Lambda; once you have its limit, you transform and read off the rate function exactly as in Cramer.
The steepness hypothesis (essential smoothness: Lambda differentiable on the interior of its finite domain, with gradient blowing up at the boundary) is the condition that cannot be dropped — it is what guarantees the full lower bound and that the rate function is the genuine Legendre transform rather than only its convex hull lower bound. Without essential smoothness, Gartner-Ellis still delivers the upper bound with rate Lambda*, but the lower bound can fail and the true rate function may be non-convex and strictly larger than Lambda* at some points, since Legendre duality can only ever produce a convex function.
For an additive functional of a finite irreducible Markov chain, Sum f(X_k)/n, the scaled CGF Lambda(theta) equals log of the Perron-Frobenius (largest) eigenvalue of the tilted transition matrix P with entries P(i,j) e^(theta f(j)). Differentiating this eigenvalue and Legendre-transforming yields the rate function for the time average — a calculation impossible by iid Cramer because the X_k are dependent.
Dependence is absorbed into one limiting cumulant function Lambda; then transform.
Essential smoothness (steepness) of Lambda is required for the full LDP. Without it you generally still get the upper bound with rate Lambda*, but the lower bound and convexity of the true rate function can fail, and Lambda* may underestimate the real cost.