Large Deviations Theory

the large-deviation upper and lower bounds

An LDP is not a single equality but a matched pair of inequalities, and understanding why it must be split this way is the conceptual key to the whole subject. The exponential rate of a probability is governed by the cheapest (lowest-rate) outcome inside a set, but whether the boundary of the set counts depends on whether the set is open or closed — and these can give different answers. So the principle is stated as an upper bound for closed sets and a lower bound for open sets.

The upper bound says: for every closed set F, limsup (1/n) log mu_n(F) <= - inf_{x in F} I(x). Intuitively, the probability of landing in F cannot be larger than e to the minus n times the cost of F's cheapest point; the closed-set requirement is what lets you control the boundary. The lower bound says: for every open set G, liminf (1/n) log mu_n(G) >= - inf_{x in G} I(x). Here openness gives you room to find a small neighbourhood around a near-optimal point and lower-bound its probability. When a set A has inf I over its interior equal to inf I over its closure (an I-continuity set), both bounds collapse to a genuine limit and you may write lim (1/n) log mu_n(A) = - inf_{x in A} I(x).

The two halves are proven by genuinely different techniques and one is usually harder than the other. The upper bound on compacts typically comes from a Chebyshev-style exponential Markov inequality optimised over a tilting parameter, then extended to closed sets via exponential tightness; the lower bound comes from an exponential change of measure (tilting) that makes the target deviation typical, after which an ordinary law of large numbers does the work. Forgetting that the upper bound needs closedness (or compactness plus tightness) and the lower bound needs openness is the most common source of wrong large-deviation statements.

Take the singleton {x_0} (closed) versus its open neighbourhoods. The upper bound on the closed point {x_0} gives <= -I(x_0); but the lower bound on the closed point is useless because {x_0} has empty interior. To get a matching lower bound you must use an open ball B(x_0, r), and only then let r -> 0, using lower semicontinuity of I.

Upper bound on closed sets, lower bound on open sets — they meet only on continuity sets.

The two bounds need not match for every set: if inf_interior I > inf_closure I (a non-continuity set), the limit of (1/n) log mu_n(A) may not exist or may sit strictly between them. The LDP only promises a true limit on I-continuity sets.

Also called
LDP upper boundLDP lower boundLaplace-Varadhan bounds