Large Deviation Principle and Cramér's Theorem

1. Beyond the Central Limit Theorem

We've already studied two fundamental results concerning the sum of independent and identically distributed (IID) random variables, $S_n=\frac{1}{n}{\sum }_{i=1}^n{X}_i$:

1. The Law of Large Numbers (LLN): As $n\to \infty$, the sample mean $S_n$ converges to the true mean, $E[X]=\mu$.
2. The Central Limit Theorem (CLT): The fluctuations of $S_n$ around the mean $\mu$ on the scale of $1/\sqrt{n}$ are described by a Gaussian distribution.

The CLT describes typical, small fluctuations. But what about atypical, large fluctuations? What is the probability that $S_n$ takes on a value $a$ that is significantly different from $\mu$? The LLN tells us this probability goes to zero as $n\to \infty$, but it doesn't say how fast. This is the question that Large Deviation Theory (LDT) answers.

Professor Frank den Hollander provides an excellent introduction to this idea.

As the video explains, LDT states that the probability of observing a large deviation decays exponentially with $n$:

The function $I(a)$ is called the rate function. It quantifies the "cost" or improbability of observing the deviation $a$.

2. The Large Deviation Principle

Let's formalize this intuition. The two provided texts by Hugo Touchette, written from a physicist's perspective, offer a clear and rigorous development of the theory.

The working definition of the LDP for a sequence of random variables $A_n$ is that the limit

exists and defines the rate function $I(a)$. From this definition and the examples, we can deduce some key properties of the rate function:

• Positivity: $I(a)\ge 0$. A negative rate would imply a probability greater than 1.
• Zeroes correspond to typical values: If the system obeys the Law of Large Numbers and converges to a value $\mu$, then $I(\mu )=0$, and $I(a)>0$ for $a\ne \mu$. The most probable event has zero "cost."
• Convexity: Rate functions are typically convex. The region around the minimum $a=\mu$ is approximately quadratic, $I(a)\approx \frac{1}{2}{I}^{\prime \prime }(\mu )(a-\mu {)}^2$. This recovers the Gaussian form of the Central Limit Theorem for small deviations. LDT thus contains the CLT as a special case but also describes the non-Gaussian tails for large deviations.

For a fully rigorous mathematical statement, the LDP is defined not with a simple limit but with a lower bound for open sets and an upper bound for closed sets. This is analogous to how weak convergence of probability measures is defined.

3. Calculating the Rate Function: Cramér's Theorem

We now have a definition for the rate function, but how do we compute it without first knowing the full probability distribution $P(A_n\approx a)$? The cornerstone result that connects LDT to a calculable quantity is the Gärtner-Ellis Theorem.

This theorem introduces the scaled cumulant generating function (SCGF), $\lambda (k)$:

The Gärtner-Ellis theorem states that if $\lambda (k)$ exists and is differentiable, then the rate function $I(a)$ is its Legendre-Fenchel transform:

This structure is profoundly important. You have encountered the Legendre transform in the transition from the Lagrangian to the Hamiltonian in classical mechanics, and you will soon see it connecting different thermodynamic potentials (like entropy and free energy) in statistical mechanics. Here, it connects the statistical properties of fluctuations ($I(a)$) to a generating function ($\lambda (k)$). The "plausibility proof" in the following reading shows that this theorem is essentially a consequence of applying the saddle-point method to the definition of the generating function, which provides a beautiful link to our previous lesson.

Cramér's Theorem (also known as the Chernoff-Cramér theorem) is the direct application of this machinery to the case we are most interested in: the sum of IID random variables, $S_n=\frac{1}{n}{\sum }_{i=1}^n{X}_i$.

For IID variables, the SCGF simplifies significantly:

So, $\lambda (k)$ is simply the logarithm of the moment-generating function of a single variable $X$.

Cramér's Theorem states: The sample mean $S_n$ of IID random variables satisfies a large deviation principle with a rate function $I(a)$ given by:

The following video segment formally states this theorem and provides several key examples.

The graph below provides a visual confirmation of Cramér's theorem. It plots the logarithm of the probability of a large deviation against $n$. According to the LDP, this should be a straight line for large $n$, with a slope equal to $-I(a)$. The plot shows that the LDP estimate (blue line) is an excellent approximation to the exact bounds for large $n$.

4. Sanov's Theorem: A Bridge to Information Theory

Cramér's theorem concerns the sample mean, a single number. But LDT can also be applied to more complex objects. A particularly insightful application is Sanov's Theorem, which describes the large deviations of the entire empirical probability distribution.

Let $L_n$ be the histogram or empirical distribution we observe from $n$ samples. The LLN implies that as $n\to \infty$, $L_n$ converges to the true underlying distribution $P$. Sanov's theorem answers: what is the probability that the observed empirical distribution is close to some other distribution $Q$? The result is:

The rate function is $D(Q||P)$, the Kullback-Leibler (KL) divergence or relative entropy between the distributions $Q$ and $P$.

This provides a profound connection back to our very first lesson on information theory. The KL divergence, which we saw as a measure of "distance" between two probability distributions, is precisely the rate function governing the probability of observing one distribution when the true one is another.

The derivation of Sanov's theorem from combinatorics and Stirling's approximation is a beautiful exercise.

This result is a cornerstone of the connection between statistical mechanics and information theory. As we will see later, principles like maximizing entropy can be understood as finding the state with the highest probability (lowest rate function) subject to certain constraints.

Conclusion

This lesson concludes our foundational module on probability and asymptotic methods. We have moved from the law of large numbers (the most likely outcome) and the central limit theorem (small fluctuations) to the powerful framework of large deviation theory, which quantifies the probability of rare but important events.

Key Takeaways:

• The Large Deviation Principle states that the probability of an atypical macroscopic state decays exponentially, $P(A_n\approx a)\approx e^{-nI(a)}$.
• The rate function $I(a)$ is a non-negative, convex function that is zero only for the most probable state(s).
• Cramér's Theorem provides a direct method for calculating the rate function for sums of IID random variables. It is the Legendre-Fenchel transform of the scaled cumulant generating function: $I(a)={\sup }_k\{ka-\lambda (k)\}$.
• The mathematical structure of LDT, particularly the Legendre transform, mirrors the structure of thermodynamics, connecting fluctuation probabilities to free energies.
• Sanov's Theorem shows that the rate function for the empirical distribution is the KL divergence, linking LDT directly to information theory.

You have now built a formidable mathematical arsenal. We are ready to leave the realm of pure probability and enter the world of physics. In the next module, Kinetic Theory, we will apply these ideas for the first time to a physical system: a dilute gas. We will derive the Boltzmann equation to describe how collisions between particles drive the system towards equilibrium, providing the first microscopic justification for the emergence of irreversible, macroscopic behavior.