Flip a fair coin a thousand times and count the heads. The law of large numbers says you will get about 500, and the central limit theorem says the typical error is around 16. Neither one tells you the probability of 900 heads. If you push the Gaussian approximation out that far anyway, it returns something like \(10^{-141}\). The true answer is close to \(10^{-161}\). The bell curve is off by twenty orders of magnitude, in a regime where insurers, engineers and physicists have real questions.
Large deviations is the part of probability that gets such numbers right. Its basic statement is that the chance of an average landing on an atypical value \(x\) decays exponentially in the number of samples,
$$\mathbb P\Big(\frac1n\sum_{i=1}^n X_i \approx x\Big)\;\asymp\; e^{-n\,I(x)},$$
with a rate function \(I\) that can be computed. The symbol \(\asymp\) says that the two sides agree on the exponential scale: take the logarithm of each, divide by \(n\), and the results have the same limit. It fixes the exponent and ignores every factor that grows or shrinks more slowly than an exponential. The \(\approx\) inside the probability means that the average lands in a small window around \(x\). The same kind of statement, with a different \(I\), holds for histograms of samples, for the paths of a diffusion with weak noise, and for most situations in which many small random contributions add up.
The first reason for this essay is a debt. In the Fokker–Planck essay I quoted Kramers' law, that a particle escapes a well of depth \(\Delta V\) after a time of order \(e^{\Delta V/T}\), and gave no derivation. In the control essay the main theorem rested on a fact that I waved through in a side note: minimizing an expected cost plus a KL penalty gives a Boltzmann-tilted distribution, and the minimal value is a free energy. Both are large deviations statements. The second has a name, the Gibbs variational principle, and it is the equation under the title.
The second reason is that this is where probability turns into optimization. A rare event, when it does happen, happens in a particular way, and that way solves a minimization problem. Of all the routes to the event, the cheapest one carries nearly all the probability. By Part IV the minimization will be an optimal control problem and the rate function will be its value function. So the control essay and this one are about the same equation, read at two temperatures.
Here is the plan. Part I does coins and dice by hand and proves Cramér's theorem. Part II is about the Legendre transform, the piece of convex analysis that does the work in Part I, and derives the title equation on a finite set. Part III says what a large deviation principle is in general, and shows that the title equation is the one case of the general theory that is exact with no limit taken. Part IV is about diffusions with weak noise, and about control. Part V collects what reinforcement learning does with all of it. As in the other essays, underlined terms open derivations, and the figures respond to you.
Let \(S_n\) be the number of heads in \(n\) flips of a coin that lands heads with probability \(p\). The probability of exactly \(k\) heads is \(\binom nk p^k(1-p)^{n-k}\). Put \(k=xn\), take logarithms, and use on the binomial coefficient. What comes out is
Stirling: \(\log n! = n\log n - n + \tfrac12\log(2\pi n) + o(1)\). Applied three times,
$$\log\binom{n}{xn} \;=\; n\,H(x)\;-\;\tfrac12\log\!\big(2\pi n\,x(1-x)\big)+o(1),$$
where \(H(x)=-x\log x-(1-x)\log(1-x)\) is the entropy of a coin with bias \(x\).
The remaining factor contributes \(n\,[\,x\log p+(1-x)\log(1-p)\,]\). Adding the two,
$$\log \mathbb P(S_n=xn) \;=\; -\,n\,I(x)\;-\;\tfrac12\log\!\big(2\pi n\,x(1-x)\big)+o(1),$$
with \(I(x)=x\log\frac xp+(1-x)\log\frac{1-x}{1-p}\) as in the main text.
The first term is of order \(n\). The second is of order \(\log n\), and it is the reason the dots in Figure 1 sit slightly above the curve and sink onto it slowly.
$$\mathbb P(S_n = xn)\;\asymp\;e^{-n\,I(x)},\qquad I(x)\;=\;x\log\frac{x}{p}+(1-x)\log\frac{1-x}{1-p}.$$
The symbol is the one from the introduction, equality of \(\frac1n\log\) in the limit. The exponent is a relative entropy, \(I(x)=\mathrm{KL}\big(\mathrm{Ber}(x)\,\|\,\mathrm{Ber}(p)\big)\), the divergence of the coin you would need from the coin you have. It is zero at \(x=p\), positive everywhere else, and convex.
I write \(a_n\asymp b_n\) when \(\frac1n\log a_n-\frac1n\log b_n\to0\). When the left side is a probability of the form \(\mathbb P(Z_n\approx z)\), the window around \(z\) is held fixed while \(n\to\infty\) and shrunk afterwards. Part III gives the version of this with open and closed sets. This forgets every factor that grows or decays more slowly than an exponential. All of \(5\,e^{-nI}\), \(n^{-1/2}e^{-nI}\) and \(e^{-nI+\sqrt n}\) are \(\asymp e^{-nI}\).
That is a weak notion of equality, and it is the level at which the theory is clean. Exponents are robust and come from a variational formula. Prefactors depend on the details of the model and are much harder. For \(n=30\) a forgotten prefactor can matter more than the exponent, and the coda comes back to this.
Left: the distribution of the fraction of heads, on a linear scale. Right: the same probabilities as \(-\frac1n\log\mathbb P\). The green dots are exact binomial values, with nothing approximated.
On a linear scale all you can see is a bell getting narrower, because everything outside the bell is indistinguishable from zero. On the scale of \(-\frac1n\log\mathbb P\) the same numbers line up along a curve that stops moving as \(n\) grows. That curve is what this essay studies. The dashed parabola is \((x-p)^2/2p(1-p)\), the exponent you get by trusting the central limit theorem at every \(x\). It matches \(I\) to second order at \(x=p\) and nowhere else, and the mismatch is the twenty orders of magnitude from the introduction.
The two theorems do not overlap. The central limit theorem describes deviations of size \(n^{-1/2}\), where \(n\,I(x)\) is of order one and \(\asymp\) has already thrown it away. Large deviations describes deviations of size one, where the Gaussian has no authority. That the curvature of \(I\) at its minimum is one over the variance is a consistency between two statements about different regimes, and neither implies the other.
Stirling's formula needs something to count. In 1938 Harald Cramér, who worked on insurance risk and needed tail probabilities for total claims, found an argument that works for sums \(S_n=X_1+\dots+X_n\) of any independent, identically distributed variables with light tails. It has two halves, and I want to keep them apart because Part IV reuses the second half on its own.
Both halves use the of one sample,
\(\Lambda(\theta)=\log\mathbb E[e^{\theta X}]\) is the logarithm of the moment generating function. It has \(\Lambda(0)=0\), \(\Lambda'(0)=\mathbb E[X]\) and \(\Lambda''(0)=\mathrm{Var}(X)\), and its higher derivatives at zero are the higher cumulants. It is convex: \(\Lambda''(\theta)\) is the variance of \(X\) under the tilted law defined below, which cannot be negative.
For a coin with bias \(p\) it is \(\log(1-p+p\,e^{\theta})\). For a standard Gaussian it is \(\theta^2/2\).
The standing assumption is that \(\Lambda\) is finite in a neighbourhood of \(\theta=0\), which says that the tails of \(X\) decay at least exponentially. Without it the argument fails and so does the theorem. The coda says what replaces it.
$$\Lambda(\theta)\;=\;\log \mathbb E\big[e^{\theta X}\big].$$
Upper bound. For any \(\theta\ge0\), Markov's inequality applied to \(e^{\theta S_n}\) gives
$$\mathbb P(S_n\ge nx)\;\le\;e^{-\theta n x}\;\mathbb E\big[e^{\theta S_n}\big]\;=\;e^{-n\,(\theta x-\Lambda(\theta))}.$$
This is true for every \(\theta\ge0\) and every \(n\), so take the best \(\theta\). For \(x\) above the mean, restricting to \(\theta\ge0\) , and the result is the Chernoff bound
By Jensen's inequality \(\Lambda(\theta)\ge\theta\,m\), where \(m=\mathbb E[X]\). So for \(\theta<0\) and \(x>m\), \(\theta x-\Lambda(\theta)\le\theta(x-m)<0\), which is worse than the value \(0\) at \(\theta=0\). The supremum over all real \(\theta\) is therefore attained at some \(\theta\ge0\). For \(x\) below the mean the mirror-image argument bounds \(\mathbb P(S_n\le nx)\) with \(\theta\le0\).
$$\mathbb P(S_n\ge nx)\;\le\;e^{-n\,I(x)},\qquad I(x)\;=\;\sup_{\theta}\big\{\theta x-\Lambda(\theta)\big\}.$$
Lower bound. An upper bound could be loose. To show that this one is tight on the exponential scale you have to exhibit a way for the event to happen and work out what that way costs. The way is to change the distribution. Define the
The tilted law \(\mu_\theta\) is a probability measure, since \(e^{\Lambda(\theta)}\) is by definition the normalizer of \(e^{\theta y}\mu(\mathrm dy)\). Differentiating \(\Lambda\) under the expectation gives
$$\Lambda'(\theta)=\mathbb E_{\mu_\theta}[X],\qquad \Lambda''(\theta)=\mathrm{Var}_{\mu_\theta}(X).$$
So as \(\theta\) increases, the mean of \(\mu_\theta\) increases with it, and in every example of this essay it sweeps through all the values the average could take. Its relative entropy to the original law is
$$\mathrm{KL}(\mu_\theta\,\|\,\mu)=\mathbb E_{\mu_\theta}\big[\theta X-\Lambda(\theta)\big]=\theta\,\Lambda'(\theta)-\Lambda(\theta).$$
Now pick \(\theta\) so that \(\Lambda'(\theta)=x\). That is the stationarity condition for \(\sup_\theta\{\theta x-\Lambda(\theta)\}\), and since the bracket is concave in \(\theta\) it is the maximizer. Hence \(\mathrm{KL}(\mu_\theta\|\mu)=\theta x-\Lambda(\theta)=I(x)\). For a coin, tilting \(\mathrm{Ber}(p)\) multiplies the odds of heads by \(e^{\theta}\), and the tilt with mean \(x\) is \(\mathrm{Ber}(x)\).
$$\mu_\theta(\mathrm dy)\;=\;e^{\theta y-\Lambda(\theta)}\,\mu(\mathrm dy),$$
and pick \(\theta\) so that its mean is \(x\). Under the tilted law the event \(\{S_n\approx nx\}\) is ordinary. Probabilities under the two laws differ by a likelihood ratio, and on that event the ratio is \(e^{-n(\theta x-\Lambda(\theta))}\) up to a factor that does not grow exponentially. , this is a matching lower bound.
Let \(\mathbb P_\theta\) be the law under which the \(X_i\) are i.i.d. from \(\mu_\theta\). For any event \(A\) that depends on the first \(n\) samples,
$$\mathbb P(A)\;=\;\mathbb E_\theta\Big[e^{-\theta S_n+n\Lambda(\theta)}\,\mathbf 1_A\Big].$$
Take \(A=\{x\le S_n/n\le x+\delta\}\) and \(\theta\ge0\) with \(\Lambda'(\theta)=x\). On \(A\) the exponent is at least \(-n(\theta(x+\delta)-\Lambda(\theta))\), so
$$\mathbb P(A)\;\ge\;e^{-n(I(x)+\theta\delta)}\;\mathbb P_\theta(A).$$
Under \(\mathbb P_\theta\) the average has mean \(x\), so by the central limit theorem \(\mathbb P_\theta(A)\to\tfrac12\). Therefore \(\liminf\frac1n\log\mathbb P(A)\ge-I(x)-\theta\delta\), and \(\delta\) was arbitrary. The central limit theorem enters here as a tool. After tilting, the rare event is a typical one, and typical events are its department.
$$\boxed{\;\mathbb P\Big(\frac{S_n}{n}\approx x\Big)\;\asymp\;e^{-n\,I(x)},\qquad I(x)\;=\;\sup_{\theta}\big\{\theta x-\Lambda(\theta)\big\}\;}$$
This is Cramér's theorem. Read the lower bound again as a statement about cost. The fair coin does not produce 70% heads. A coin with bias 0.7 does so routinely. The probability that the fair coin imitates the biased one for \(n\) flips is the likelihood ratio between them, and per flip the logarithm of that ratio averages to \(\mathrm{KL}(\mu_\theta\,\|\,\mu)\), which is exactly \(I(x)\). I claim further that among all distributions that would make the event typical, the exponential tilt is the cheapest to imitate. Part III proves that.
Exponential tilting has been found many times. Actuaries call it the Esscher transform, after a 1932 paper. Statisticians call the family \(\{\mu_\theta\}\) an exponential family. A physicist would say that \(\mu_\theta\propto e^{\theta y}\mu\) is a Boltzmann distribution with energy \(-y\) and inverse temperature \(\theta\), and that \(\Lambda\) is the logarithm of a partition function. Hold on to the physicist's reading for Part II.
The tilt also describes what you would see if you watched. Condition on \(S_n\ge nx\) and look at one of the samples. As \(n\) grows, its conditional law converges to \(\mu_\theta\). This is the . A fair coin that came up 70% heads did it by looking, flip for flip, like a 0.7 coin. There are other ways to reach 70%, such as an opening streak of heads followed by ordinary flipping. They are possible, and their probability is smaller by a factor exponential in \(n\).
The statement: if \(\Lambda'(\theta)=x\) and \(x\) is above the mean, then for every fixed \(k\) the conditional law of \((X_1,\dots,X_k)\) given \(S_n\ge nx\) converges to \(\mu_\theta^{\otimes k}\) as \(n\to\infty\). A finite handful of the samples look like independent draws from the tilt.
For a constraint on the average of a function of the samples this is due to Van Campenhout and Cover (1981). Csiszár (1984) proved it for general convex constraints on the empirical measure, with the tilt replaced by the distribution in the constraint set that is closest to \(\mu\) in relative entropy. Part III puts it in that form.
The reason is the one in the main text. Conditioning on an event of probability \(e^{-nI}\) selects the cheapest way of producing it, and any way other than uniform tilting costs strictly more per sample.
E. T. Jaynes used a die to make a point about inference, in lectures at Brandeis in 1962. A die has been rolled many times and all you are told is that the average was 4.5 where a fair die gives 3.5. The question is what probabilities to assign to the faces. Jaynes's answer was the distribution of maximum entropy with that mean, \(p_k\propto e^{\theta k}\) with \(\theta\approx0.371\), and he defended it as a principle of reasoning. If the die is in fact fair and the high average is a fluke, no principle is required. The conditional limit theorem says the faces will be distributed that way, and you can check by rolling dice and throwing out the runs that fail.
Fair dice are rolled in runs of \(n\). A run is kept only if its average is at least \(a\). The bars count faces in the kept runs, and the blue marks are the exponential tilt with mean \(a\).
Raise \(n\) and the bars settle onto the blue marks while the fraction of runs that pass collapses. The readout compares that fraction with \(e^{-nI(a)}\). The measured exponent sits a little above \(I(a)\) and comes down toward it as \(n\) grows, which is the forgotten prefactor showing itself. Rejection sampling of a rare event costs about \(e^{nI}\) samples per success, and that is the practical reason to care about the tilt, since sampling from \(\mu_\theta\) directly costs nothing. The control essay made the same comparison in its last figure, between throwing away passive paths and steering them. Part IV explains why it is the same comparison.
The formula \(I(x)=\sup_\theta\{\theta x-\Lambda(\theta)\}\) arrived in Part I as the result of optimizing a bound. The operation has a name and a geometry, and the rest of the essay uses both.
For a function \(f\) on \(\mathbb R^d\), its Legendre transform, or convex conjugate, is
$$f^{*}(p)\;=\;\sup_{x}\big\{\langle p,x\rangle-f(x)\big\}.$$
In one dimension the picture is as follows. A convex function can be described by its graph, which records a height for each point. It can also be described by its tangent lines, by recording an intercept for each slope. The line of slope \(p\) that touches the graph of \(f\) from below crosses the vertical axis at height \(-f^{*}(p)\). So \(f^{*}\) is the same curve, indexed by slope.
about the transform are enough for this essay. The transform of any function is convex. Applying it twice returns the original function if that function was convex, and returns its convex hull otherwise. The derivatives \(f'\) and \((f^{*})'\) are inverse to each other, so the variable of \(f^{*}\) is the slope of \(f\). And for all \(x\) and \(p\), \(f(x)+f^{*}(p)\ge\langle p,x\rangle\), with equality exactly when \(p\) is the slope of \(f\) at \(x\).
Convexity. For each fixed \(x\), the map \(p\mapsto\langle p,x\rangle-f(x)\) is affine. A supremum of affine functions is convex. This needs nothing from \(f\).
Fenchel–Young. The inequality \(f(x)+f^{*}(p)\ge\langle p,x\rangle\) is the definition of the supremum, rearranged. Equality holds when \(x\) attains the supremum, which for differentiable convex \(f\) means \(p=\nabla f(x)\).
Inverse derivatives. If \(x(p)\) is the maximizer, then \(f^{*}(p)=\langle p,x(p)\rangle-f(x(p))\) and differentiating in \(p\) gives \(\nabla f^{*}(p)=x(p)\), the other terms cancelling by stationarity. So \(\nabla f^{*}=(\nabla f)^{-1}\), and in one dimension the second derivatives are reciprocal: \((f^{*})''(p)=1/f''(x)\). For Cramér's pair this reads \(I''(x)=1/\mathrm{Var}_{\mu_\theta}(X)\), which at the mean is one over the variance. That is the parabola in Figure 1.
Biconjugate. \(f^{**}\) is the largest convex, lower semicontinuous function below \(f\). If \(f\) already is convex and lower semicontinuous then \(f^{**}=f\) (Fenchel–Moreau). If \(f\) has a dent, \(f^{**}\) bridges it with a straight segment.
In the vocabulary of Part I, \(\Lambda\) and \(I\) are a Legendre pair. The tilt parameter \(\theta\) is the slope of \(I\), the mean \(x\) is the slope of \(\Lambda\), and the tilt that makes \(x\) typical is \(\theta=I'(x)\).
Left: \(\Lambda(\theta)\). Right: the rate function. Drag in either panel. The tangent on each side has the other side's horizontal coordinate as its slope and minus the other side's height as its intercept.
The last preset is in the menu to show a failure. It is a magnet below its critical temperature, the Curie–Weiss model that Part III computes, and its true rate function has two wells. Its \(\Lambda\) has a corner at \(\theta=0\). Transform \(\Lambda\) back and you get the dashed green curve, which is flat between the wells. The transform returned the convex hull of the rate function, and the barrier is gone. Any method that computes \(\Lambda\) first and transforms second has this blind spot. The general theorem of that type, due to Gärtner and Ellis, guards against it by requiring \(\Lambda\) to be differentiable. Physicists know the flat piece as the Maxwell construction. It is also the pitchfork from Part IV of the Fokker–Planck essay, seen from the other side of the transform.
Most physicists meet this transform in thermodynamics, usually without its name. The internal energy \(U(S,V)\) is a function of entropy and volume, and temperature is defined as a slope, \(T=\partial U/\partial S\). A thermometer is easier to operate than an entropy meter, so one would like the slope as the independent variable. The Legendre transform does that:
$$F(T,V)\;=\;\inf_{S}\big\{U(S,V)-T\,S\big\}.$$
This is the Helmholtz free energy, \(F=U-TS\) evaluated at the entropy where the slope of \(U\) is \(T\). Doing the same to the other pair, the volume and its slope \(-P\), gives the enthalpy \(H=U+PV\). Doing both gives the Gibbs free energy \(G=U-TS+PV\). The four potentials sit on a square whose edges are Legendre transforms.
Each corner holds the same information, arranged for a different experiment: an insulated rigid box, a rigid box in a heat bath, an insulated cylinder under a piston, a beaker open to the room. The top edge is the one this essay needs. In statistical mechanics it connects the entropy as a function of energy with the free energy as a function of temperature, and . Entropy is a rate function, the logarithm of the partition function is a cumulant generating function, and inverse temperature is a tilt parameter.
Take \(n\) particles whose energies \(\varepsilon_i\) are independent under an a priori measure \(\mu\), for instance the uniform measure on single-particle states. Cramér's theorem for the mean energy says \(\mathbb P\big(\frac1n\sum\varepsilon_i\approx E\big)\asymp e^{-nI(E)}\) with \(I(E)=\sup_\theta\{\theta E-\Lambda(\theta)\}\). Write \(\theta=-\beta\). Then \(\Lambda(-\beta)=\log\mathbb E_\mu[e^{-\beta\varepsilon}]=\log Z(\beta)\), the logarithm of the single-particle partition function, and
$$-I(E)\;=\;\inf_{\beta}\big\{\beta E+\log Z(\beta)\big\}.$$
The left side is \(\frac1n\log\) of the fraction of configurations with energy per particle \(E\), which is Boltzmann's entropy per particle \(s(E)\) up to an additive constant. Writing \(\log Z=-\beta f\) for the free energy per particle \(f\), this reads \(s(E)=\inf_\beta\{\beta E-\beta f(\beta)\}\), and inverting the transform, \(\beta f(\beta)=\inf_E\{\beta E-s(E)\}\). At the minimizing \(E\) that is \(f=E-Ts\). This is the top edge of the square, per particle and with Boltzmann's constant set to one.
The minimizing \(\beta\) is the one at which the canonical mean energy is \(E\). It is the tilt parameter of Part I. Physicists call the resulting agreement between conditioning on the energy and tilting by it the equivalence of ensembles, and in Part I's terms it is the conditional limit theorem. It fails when \(s\) is not concave, which happens in some systems with long-range forces, and the failure is the one shown by the magnet preset in Figure 3.
Now the computation that the title equation comes from. Take a finite set of \(k\) states, a vector \(x\in\mathbb R^k\), and the function
$$f(x)\;=\;\mathrm{LSE}(x)\;=\;\log\sum_{i}e^{x_i}.$$
I want its Legendre transform \(f^{*}(p)=\sup_x g_p(x)\), where \(g_p(x)=\langle x,p\rangle-f(x)\). The function \(f\) is , so \(g_p\) is linear minus convex, hence concave, and any stationary point is a maximum. The gradient is
The Hessian of \(\mathrm{LSE}\) at \(x\) is \(\mathrm{diag}(s)-ss^{\top}\) with \(s=\mathrm{softmax}(x)\). That is the covariance matrix of a one-hot random vector drawn from \(s\), so it is positive semidefinite.
It has exactly one direction of zero curvature, \((1,\dots,1)\): adding a constant \(c\) to every \(x_i\) adds \(c\) to \(f\). A direction along which \(f\) is affine shows up in \(f^{*}\) as a constraint, and here the constraint is \(\sum_ip_i=1\). In physical terms, shifting all energies by a constant changes nothing, and probabilities sum to one. These are one fact, seen from the two sides of the transform.
$$\nabla_x\,g_p(x)\;=\;p-\mathrm{softmax}(x),$$
which vanishes when
$$p_i=\frac{e^{x_i}}{\sum_je^{x_j}}\qquad\Longleftrightarrow\qquad x_i=\log p_i+f(x).$$
This can be solved for \(x\) only when \(p\) is a probability vector with positive entries. the supremum is \(+\infty\) or is reached as a limit. Substitute, and use \(\sum_ip_i=1\):
If \(\sum_ip_i\ne1\), move \(x\) along \((1,\dots,1)\): \(g_p(x+c\mathbf 1)=g_p(x)+c\,(\sum_ip_i-1)\), which is unbounded in one direction of \(c\). If some \(p_i<0\), send \(x_i\to-\infty\): the term \(x_ip_i\) goes to \(+\infty\) while \(f\) stays bounded below by the other coordinates. In both cases \(f^{*}(p)=+\infty\).
If \(p\) is a probability vector with some zero entries, no stationary point exists, but sending the corresponding \(x_i\to-\infty\) approaches the value \(\sum_ip_i\log p_i\) with the convention \(0\log0=0\). So \(f^{*}(p)=-H(p)\) on the closed simplex and \(+\infty\) off it.
$$f^{*}(p)\;=\;\langle\log p,\,p\rangle+f(x)-f(x)\;=\;\sum_ip_i\log p_i\;=\;-H(p).$$
The conjugate of log-sum-exp is negative entropy on the simplex. Softmax and the logarithm are the two derivative maps, inverse to each other up to an additive constant.
Since \(f\) is convex and continuous, transforming twice gives it back:
$$\log\sum_ie^{x_i}\;=\;\sup_{p}\big\{\langle x,p\rangle+H(p)\big\}.$$
Set \(x=-U/T\) for a vector of energies \(U\) and a temperature \(T\), so that \(\langle x,p\rangle=-\mathbb E_p[U]/T\), and multiply through by \(-T\):
$$\boxed{\;-\,T\log\sum_ie^{-U_i/T}\;=\;\inf_{p}\Big\{\mathbb E_p[U]-T\,H(p)\Big\}\;}$$
with the infimum attained at \(p_i\propto e^{-U_i/T}\). This is Theorem 1 of the Fokker–Planck essay, that the Boltzmann distribution minimizes \(F=E-TS\). There I proved it with a Lagrange multiplier. The Legendre proof gives more for the same work. It says that the minimal free energy, as a function of the energies, and the entropy, as a function of the probabilities, are conjugate, so either one can be recovered from the other.
The finite computation used counting measure without saying so. Replace it by any probability measure \(\mu\) on any space, replace the vector \(x\) by a function \(f\), and the same pair of formulas holds:
$$\log\mathbb E_\mu\big[e^{f}\big]\;=\;\sup_{\nu}\Big\{\mathbb E_\nu[f]-\mathrm{KL}(\nu\,\|\,\mu)\Big\},$$
$$\mathrm{KL}(\nu\,\|\,\mu)\;=\;\sup_{f}\Big\{\mathbb E_\nu[f]-\log\mathbb E_\mu\big[e^{f}\big]\Big\}.$$
The first line is the Gibbs variational principle. The second is the Donsker–Varadhan formula for relative entropy, from their papers of the 1970s. They are one Legendre pair written in both directions, with functions and measures put in duality by \(\langle f,\nu\rangle=\mathbb E_\nu[f]\). Both follow from . Let \(\mu_f=e^{f}\mu\,/\,\mathbb E_\mu[e^{f}]\) be the tilt of \(\mu\) by \(f\). Then for every \(\nu\),
By definition \(\log\frac{\mathrm d\mu_f}{\mathrm d\mu}=f-\log\mathbb E_\mu[e^{f}]\). So for any \(\nu\) with a density against \(\mu\),
$$\mathrm{KL}(\nu\,\|\,\mu_f)=\mathbb E_\nu\Big[\log\frac{\mathrm d\nu}{\mathrm d\mu}-\log\frac{\mathrm d\mu_f}{\mathrm d\mu}\Big]=\mathrm{KL}(\nu\,\|\,\mu)-\mathbb E_\nu[f]+\log\mathbb E_\mu[e^{f}].$$
The left side is nonnegative and vanishes only at \(\nu=\mu_f\). Fix \(f\) and vary \(\nu\): this is the first formula, with the supremum attained at the tilt. Fix \(\nu\) and vary \(f\): the bracket in the second formula is at most \(\mathrm{KL}(\nu\|\mu)\), with equality when \(\mu_f=\nu\), that is, at \(f=\log\frac{\mathrm d\nu}{\mathrm d\mu}\). If that \(f\) is unbounded one approaches it by truncation, and the supremum over bounded measurable \(f\) (or bounded continuous \(f\), on a reasonable space) is still the relative entropy.
Read as an inequality, \(\mathbb E_\nu[f]\le\mathrm{KL}(\nu\|\mu)+\log\mathbb E_\mu[e^{f}]\) is the Fenchel–Young inequality for this pair. It lets you bound an expectation under a measure you do not control by an exponential moment under one you do, at the price of a relative entropy.
$$\log\mathbb E_\mu\big[e^{f}\big]-\Big(\mathbb E_\nu[f]-\mathrm{KL}(\nu\,\|\,\mu)\Big)\;=\;\mathrm{KL}(\nu\,\|\,\mu_f)\;\ge\;0.$$
So the supremum in the first line is attained at \(\nu=\mu_f\) and nowhere else, and the amount by which any other \(\nu\) falls short is its relative entropy to the tilt. Theorem 2 of the Fokker–Planck essay, that excess free energy is \(T\) times the KL divergence to equilibrium, is this identity. Put \(f=-U/T\), multiply by \(-T\), and you have the equation under the title:
$$\boxed{\;-\,T\log \mathbb E_{\mu}\big[e^{-U/T}\big] \;=\; \inf_{\nu}\Big\{\mathbb E_{\nu}[U] + T\,\mathrm{KL}(\nu\,\|\,\mu)\Big\}\;}$$
With \(\mu\) uniform on \(k\) states, \(\mathrm{KL}(\nu\|\mu)=\log k-H(\nu)\) and the lemma of the last section comes back. With \(\mu\) a prior, \(-U\) a log-likelihood and \(T=1\), the left side is the negative log evidence and the bracket on the right is the negative of the evidence lower bound, which was Theorem 3 of the Fokker–Planck essay. The pair has too.
Variational inference. With prior \(\mu\) and likelihood \(p(\mathcal D\mid z)\), the first formula with \(f=\log p(\mathcal D\mid z)\) reads \(\log p(\mathcal D)=\sup_q\{\mathbb E_q[\log p(\mathcal D\mid z)]-\mathrm{KL}(q\|\mu)\}\). The bracket is the ELBO, and the gap for a given \(q\) is its KL divergence to the posterior, by the identity above.
PAC-Bayes. The inequality form, \(\mathbb E_\nu[f]\le\mathrm{KL}(\nu\|\mu)+\log\mathbb E_\mu[e^{f}]\), is known in that literature as the change of measure inequality. Taking \(\mu\) a prior over hypotheses, \(\nu\) a data-dependent posterior and \(f\) a multiple of the generalization gap is the first step of most PAC-Bayes bounds.
Estimating divergences. The second formula turns relative entropy into an optimization over functions, which a neural network can attempt. MINE (Belghazi et al., 2018) estimates mutual information this way. The estimate is a lower bound when the optimization is done on the true distributions, and has its own bias when done on finite samples.
Regularized policy updates. Part V.
Three states with energies \(0\), \(U_2\), \(U_3\). Each point of the triangle is a distribution \(p\), shaded by \(F[p]=\mathbb E_p[U]-T\,H(p)\), darker for lower. Drag the green dot. The ring is the Boltzmann distribution.
Wherever you put the dot, \(F[p]\) stays above \(-T\log Z\), and the amount by which it exceeds it equals \(T\cdot\mathrm{KL}(p\,\|\,\text{Boltzmann})\) to every digit shown. Cool the system and the ring slides to the corner with the lowest energy. Heat it and the ring moves to the centre, where entropy is largest. The first state's energy is pinned at zero because only energy differences matter, which is the flat direction of log-sum-exp again.
Parts I and II were about averages of numbers. The general theory is about any sequence of random objects that concentrates, and the cleanest example is the histogram.
Draw \(n\) samples from \(\mu\) and record their empirical measure \(L_n=\frac1n\sum_i\delta_{X_i}\), the normalized histogram. By the law of large numbers \(L_n\to\mu\). Sanov's theorem, from 1957, prices every other outcome:
$$\boxed{\;\mathbb P\big(L_n\approx\nu\big)\;\asymp\;e^{-n\,\mathrm{KL}(\nu\,\|\,\mu)}\;}$$
On a finite alphabet this is , the multinomial version of the Stirling computation in Part I. The Fokker–Planck essay's note on entropy gave Boltzmann's combinatorial reading, that entropy is \(\frac1N\log\) of the number of microscopic arrangements with given occupation fractions. That computation dates from 1877 and it is Sanov's theorem with \(\mu\) uniform. Relative entropy is what the count turns into when the cells are not equally likely.
With \(k\) symbols of probabilities \(\mu_1,\dots,\mu_k\), the chance that the histogram of \(n\) samples is exactly \(\nu\) (with every \(n\nu_j\) an integer) is multinomial:
$$\mathbb P(L_n=\nu)\;=\;\frac{n!}{\prod_j(n\nu_j)!}\;\prod_j\mu_j^{\,n\nu_j}.$$
Stirling turns the coefficient into \(e^{nH(\nu)}\) up to a polynomial factor, and the product is \(e^{n\sum_j\nu_j\log\mu_j}\). Together: \(e^{-n\sum_j\nu_j\log(\nu_j/\mu_j)}=e^{-n\,\mathrm{KL}(\nu\|\mu)}\). There are at most \((n+1)^k\) possible histograms, a polynomial number, so summing over a set of them changes nothing on the exponential scale. Information theorists call this the method of types.
On a general space there is nothing to count, and the theorem is proved by other means, one of which is the route through Part II: the Donsker–Varadhan formula identifies \(\mathrm{KL}(\cdot\|\mu)\) as the conjugate of \(f\mapsto\log\mathbb E_\mu[e^{f}]\), which is the cumulant generating function of \(L_n\) tested against \(f\). Sanov's theorem is then Cramér's theorem in infinitely many dimensions.
Each grey dot is the histogram of \(n\) samples from \(\mu\) (black dot, draggable) on three symbols. Shading and contour bands show \(\mathrm{KL}(\cdot\,\|\,\mu)\). The tinted band is the set \(A\) of histograms that give symbol 3 a share of at least \(a\).
The cloud of grey dots shrinks around \(\mu\) as \(n\) grows. Dots that fall in the rare set \(A\) are kept in green. They crowd against one point of \(A\), the one closest to \(\mu\) in relative entropy, and the crowding tightens with \(n\). The readout compares the measured exponent with the minimum of \(\mathrm{KL}(\cdot\|\mu)\) over \(A\).
A sequence of random objects \(Z_n\) satisfies a with rate function \(I\) if, for every reasonable set \(A\),
The \(Z_n\) take values in a topological space, usually a complete separable metric space. A rate function is a lower semicontinuous \(I\ge0\), and it is called good if its sublevel sets \(\{I\le c\}\) are compact. The principle consists of two bounds:
$$\limsup_{n}\frac1n\log\mathbb P(Z_n\in C)\;\le\;-\inf_{C}I\qquad\text{for every closed set }C,$$
$$\liminf_{n}\frac1n\log\mathbb P(Z_n\in O)\;\ge\;-\inf_{O}I\qquad\text{for every open set }O.$$
The asymmetry between open and closed sets is the same as in the definition of weak convergence of measures, and for the same reason: \(Z_n\) may sit on a lattice that misses a thin set entirely, or pile up on a boundary. When the infimum of \(I\) over the interior of \(A\) equals the infimum over its closure, the two bounds meet and \(\mathbb P(Z_n\in A)\asymp e^{-n\inf_AI}\). That is what I mean by a reasonable set.
The speed need not be \(n\). In Part IV it is \(1/T\).
$$\mathbb P(Z_n\in A)\;\asymp\;\exp\Big(-n\,\inf_{z\in A}I(z)\Big).$$
The right side depends on \(A\) only through its cheapest point. A sum of exponentially small terms is dominated by the largest one, so a set of outcomes is as likely as its least unlikely member. The rest of the theory is a set of tools for computing with this.
Contraction. If \(Z_n\) satisfies a large deviation principle with rate \(I\) and \(g\) is a continuous map, then \(g(Z_n)\) satisfies one with rate \(J(y)=\inf\{I(z):g(z)=y\}\). For \(g(Z_n)\) to land on \(y\), \(Z_n\) must land somewhere in the preimage, and it picks the cheapest spot. The mean of a histogram is a continuous function of it, at least for bounded variables, so Cramér's theorem follows from Sanov's:
$$I(x)\;=\;\inf\Big\{\mathrm{KL}(\nu\,\|\,\mu)\;:\;\int y\,\nu(\mathrm dy)=x\Big\}.$$
returns the exponential tilt and the Legendre formula. This is the proof I owed for the claim in Part I that the tilt is the cheapest distribution with the required mean.
Apply the Gibbs variational principle with \(f(y)=\theta y\). It says \(\Lambda(\theta)=\sup_\nu\{\theta\,m(\nu)-\mathrm{KL}(\nu\|\mu)\}\), where \(m(\nu)\) is the mean of \(\nu\). Group the measures \(\nu\) by their mean:
$$\Lambda(\theta)=\sup_x\Big\{\theta x-\inf_{m(\nu)=x}\mathrm{KL}(\nu\|\mu)\Big\}=\sup_x\{\theta x-J(x)\}.$$
So \(\Lambda=J^{*}\), where \(J\) is the contracted rate function. \(J\) is convex, because relative entropy is convex and the constraint is linear, so \(J=J^{**}=\Lambda^{*}=I\). The minimizer is the \(\nu\) that attains the supremum in the variational principle, which is the tilt \(\mu_\theta\).
The same argument with a Lagrange multiplier: minimize \(\mathrm{KL}(\nu\|\mu)-\theta\,(m(\nu)-x)\) over \(\nu\). The stationarity condition is \(\log\frac{\mathrm d\nu}{\mathrm d\mu}=\theta y+\text{const}\). The Legendre parameter \(\theta\) of Part I is the Lagrange multiplier of the mean constraint.
Conditioning. Given that \(L_n\) landed in \(A\), it landed near the minimizer of \(\mathrm{KL}(\cdot\|\mu)\) over \(A\), provided there is exactly one. This is the Gibbs conditioning principle, and Csiszár named the minimizer the I-projection of \(\mu\) on \(A\). The green dots above and the dice of Part I are two pictures of it. It also says what maximum entropy is in this setting. It is a description of how independent samples behave when their statistics are known to have come out atypical.
Varadhan's lemma. If \(Z_n\) satisfies a large deviation principle with rate \(I\) and \(\varphi\) is bounded and continuous, then
$$\lim_{n\to\infty}\frac1n\log\mathbb E\big[e^{\,n\,\varphi(Z_n)}\big]\;=\;\sup_{z}\big\{\varphi(z)-I(z)\big\}.$$
This is on an arbitrary space: an integral of \(e^{n(\varphi-I)}\) is governed by the maximum of the exponent. Bryc proved the converse. If the limit on the left exists for all bounded continuous \(\varphi\), and the laws are exponentially tight, then a large deviation principle holds, with rate function given by the Legendre-type formula \(I(z)=\sup_\varphi\{\varphi(z)-\lim\frac1n\log\mathbb E[e^{n\varphi(Z_n)}]\}\). So a large deviation principle and a Laplace principle are the same thing, and one may take the display above as the definition. Dupuis and Ellis built an approach to the whole subject on that choice, and Part IV follows them.
For a smooth function \(h\) on the line with a unique maximum, \(\int e^{nh(z)}\mathrm dz\asymp e^{n\max h}\): as \(n\) grows the integrand concentrates in a shrinking window around the maximizer, and the width of the window only contributes a power of \(n\).
Varadhan's lemma is this with \(\mathbb P(Z_n\in\mathrm dz)\) standing in for \(e^{-nI(z)}\mathrm dz\). Cut the space into small pieces. On each piece \(\varphi\) is nearly constant and the probability is \(\asymp e^{-n\inf I}\). Summing finitely many exponentials keeps only the largest. The tail condition in the full statement (boundedness of \(\varphi\), or a moment condition) is there so that the pieces far away cannot collectively matter.
Apply Varadhan's lemma to Sanov's theorem with the linear functional \(\varphi(\nu)=\mathbb E_\nu[f]\). Then \(n\,\varphi(L_n)=\sum_if(X_i)\), and by independence
$$\frac1n\log\mathbb E\Big[e^{\sum_if(X_i)}\Big]\;=\;\log\mathbb E_\mu\big[e^{f}\big]\qquad\text{for every }n,$$
with no limit required. The right side of the lemma is \(\sup_\nu\{\mathbb E_\nu[f]-\mathrm{KL}(\nu\|\mu)\}\). That is the Gibbs variational principle. It is the one instance of the Laplace principle that is already exact at \(n=1\), because the exponential of a linear functional of the histogram splits into independent factors.
This gives a compact description of the general theory. Large deviations is the Gibbs variational principle with the linearity dropped and a limit put in its place. Let the energy depend on the histogram nonlinearly, say through pairwise interactions between particles, so that the total energy is \(n\,\mathcal E(L_n)\) and the partition function is \(Z_n=\mathbb E\big[e^{-n\mathcal E(L_n)/T}\big]\). It no longer factorizes, and Varadhan's lemma still gives its exponential rate:
$$-\,T\lim_{n\to\infty}\frac1n\log Z_n\;=\;\inf_{\nu}\Big\{\mathcal E(\nu)+T\,\mathrm{KL}(\nu\,\|\,\mu)\Big\}.$$
The functional on the right is the free energy with an interaction term from Part IV of the Fokker–Planck essay. With a linear energy it is strictly convex and has one minimizer. With an interaction it may have several, and the is the standard example.
Take \(n\) spins \(\sigma_i=\pm1\), a priori independent and fair, with energy \(-\frac{J}{2n}\big(\sum_i\sigma_i\big)^2=-n\,\frac J2\,m_n^2\), where \(m_n\) is the mean spin. Every spin feels the average of all the others. With \(\beta=1/T\),
$$\frac{Z_n}{2^n}\;=\;\mathbb E\Big[e^{\,n\,\beta J\,m_n^2/2}\Big].$$
By Cramér's theorem \(m_n\) has rate function \(c(m)=\tfrac{1+m}2\log(1+m)+\tfrac{1-m}2\log(1-m)\), the coin's rate function in spin variables. Varadhan's lemma with \(\varphi(m)=\beta Jm^2/2\) gives
$$\lim_n\frac1n\log\frac{Z_n}{2^n}\;=\;\sup_{m}\Big\{\frac{\beta J}{2}m^2-c(m)\Big\}.$$
Stationarity reads \(\beta Jm=c'(m)=\operatorname{artanh}(m)\), that is, \(m=\tanh(\beta Jm)\). For \(\beta J\le1\) the only solution is \(m=0\). For \(\beta J>1\) there are two maximizers \(\pm m^{*}\), and the magnet has to pick one. Under the Gibbs measure, \(m_n\) has rate function \(c(m)-\beta Jm^2/2\) minus its minimum, which has two wells. That is the blue curve of the magnet preset in Figure 3, drawn for \(\beta J=1.6\). Its cumulant generating function in an external field has a corner at zero field, with one-sided slopes \(\pm m^{*}\): the spontaneous magnetization.
So far the large parameter was a number of samples. For the diffusion of the earlier essays,
$$\mathrm dX_t\;=\;b(X_t)\,\mathrm dt+\sqrt{2T}\,\mathrm dW_t,$$
the large parameter is \(1/T\). As \(T\to0\) the paths collapse onto the solution of the ordinary differential equation \(\dot\varphi=b(\varphi)\), and anything else the process does is a rare event with probability of order \(e^{-(\text{something})/T}\). Freidlin and Wentzell worked out the something in the 1970s. I will get it from the title equation, because that route shows where control comes in.
Nothing in Part II required \(\mu\) to live on a small space. Let it be \(P\), the law of the whole path \((X_t)_{0\le t\le t_f}\), and let the energy be any functional \(G\) of the path. The title equation reads
$$-\,T\log\mathbb E_P\big[e^{-G(X)/T}\big]\;=\;\inf_{Q}\Big\{\mathbb E_Q[G]+T\,\mathrm{KL}(Q\,\|\,P)\Big\},$$
with the infimum over probability laws \(Q\) on paths. Two facts from stochastic calculus make the right side concrete, and the control essay used both. A law \(Q\) has finite relative entropy to \(P\) only if it is the law of the same diffusion with added. And the relative entropy of such a law is its expected control energy, \(\mathrm{KL}(Q\|P)=\mathbb E_Q\big[\frac1{4T}\int|u_s|^2\mathrm ds\big]\). Substitute, and the temperature cancels out of the penalty:
Girsanov's theorem says that if \(Q\) is absolutely continuous with respect to \(P\), then under \(Q\) the path solves \(\mathrm dX=(b+u)\,\mathrm dt+\sqrt{2T}\,\mathrm d\widetilde W\) for some adapted process \(u\) and a \(Q\)-Brownian motion \(\widetilde W\), and
$$\log\frac{\mathrm dQ}{\mathrm dP}\;=\;\frac1{\sqrt{2T}}\int u_s\cdot\mathrm d\widetilde W_s\;+\;\frac1{4T}\int|u_s|^2\,\mathrm ds.$$
The stochastic integral has mean zero under \(Q\), so \(\mathrm{KL}(Q\|P)=\mathbb E_Q\big[\frac1{4T}\int|u_s|^2\mathrm ds\big]\). The heuristic from the control essay: over a time \(\mathrm dt\) the increment is Gaussian with variance \(2T\,\mathrm dt\), displacing its mean by \(u\,\mathrm dt\) costs \(|u\,\mathrm dt|^2/(2\cdot2T\,\mathrm dt)\) nats, and the nats add up along the path.
There is one subtlety. The process \(u\) may depend on the whole past of the path, where a controller in the usual sense uses the current state. Boué and Dupuis proved that the infimum over all \(Q\) equals the infimum over adapted controls. For a Markov problem the optimum is a feedback law anyway, the one from the control essay.
$$\boxed{\;-\,T\log\mathbb E\big[e^{-G(X)/T}\big]\;=\;\inf_{u}\;\mathbb E\Big[\,G(X^{u})+\frac14\int_0^{t_f}|u_s|^2\,\mathrm ds\Big]\;}$$
where \(X^{u}\) is the controlled process, \(\mathrm dX^{u}=(b(X^{u})+u)\,\mathrm dt+\sqrt{2T}\,\mathrm dW\). In this form the formula is due to Boué and Dupuis (1998). It is also the control problem of the previous essay with effort price \(\alpha=\tfrac12\), for which that essay's \(\lambda=2\alpha T\) equals \(T\). Its headline \(V=-\lambda\log\psi\) and the title equation here are the same statement. The left side above is \(-\lambda\log\psi\) and the right side is the definition of the value function. The control essay got there by transforming a partial differential equation and mentioned the variational argument in a side note. Here the variational argument is the main line and no differential equation is needed.
Now look at where \(T\) went. It cancelled from the cost and survives in one place, the noise that drives the controlled process. Send \(T\to0\). The controlled process becomes a deterministic path with \(\dot\varphi=b(\varphi)+u\), so \(u=\dot\varphi-b(\varphi)\), and the expectation disappears:
$$\lim_{T\to0}\;-\,T\log\mathbb E\big[e^{-G(X)/T}\big]\;=\;\inf_{\varphi}\Big\{G(\varphi)+S[\varphi]\Big\},$$
$$S[\varphi]\;=\;\frac14\int_0^{t_f}\big|\dot\varphi_t-b(\varphi_t)\big|^2\,\mathrm dt.$$
Compare with Varadhan's lemma in Part III. This is a Laplace principle for the path of the diffusion, with speed \(1/T\) and rate function \(S\), and by Bryc's converse it is a large deviation principle:
$$\mathbb P\big(X\approx\varphi\big)\;\asymp\;e^{-S[\varphi]/T}.$$
Here \(\asymp\) is read with \(1/T\) in the role of \(n\): the two sides have the same \(T\log\) as \(T\to0\). \(S\) is the Freidlin–Wentzell action. , and that work is the actual proof. The structure is visible without it, though. The rate function is a control cost because relative entropy between diffusions is control energy.
Two exchanges are buried in "send \(T\to0\)": the limit with the infimum over controls, and the convergence of a controlled diffusion with a random control to a deterministic path. The weak convergence method of Dupuis and Ellis handles both. One shows that nearly optimal controls have bounded energy, hence are tight in a weak topology, that the controlled paths converge along subsequences to solutions of the limiting ODE, and that the cost is lower semicontinuous under that convergence. The reverse inequality comes from plugging a good deterministic control into the prelimit problem.
As written the statement needs \(G\) bounded and continuous. The choice used below, \(G=0\) on a set \(A\) and \(+\infty\) off it, is reached by approximation, and that is where the open and closed sets in the definition of a large deviation principle come from.
Freidlin and Wentzell's own proof runs differently. It starts from the large deviations of Brownian motion itself (Schilder's theorem) and pushes them through the map from noise path to solution path with the contraction principle.
The probability that a weakly noisy system does something it would not do on its own is \(\exp(-\tfrac1T\,\cdot\) the least control energy that would force it to\()\).
Now the debt from the Fokker–Planck essay. Take a gradient drift \(b=-\nabla V\) and ask for the cheapest path from the bottom of a well, \(x_-\), to the saddle \(x_s\) on its rim. Expand the square with the opposite sign inside:
$$\begin{aligned}S[\varphi]&=\frac14\int\big|\dot\varphi+\nabla V\big|^2\mathrm dt\\[2pt]&=\frac14\int\big|\dot\varphi-\nabla V\big|^2\mathrm dt+\int\dot\varphi\cdot\nabla V\,\mathrm dt\;\ge\;V(x_s)-V(x_-).\end{aligned}$$
The last integral is the total change of \(V\) along the path, which is \(\Delta V\) whatever route is taken. So no escape path costs less than \(\Delta V\), and a path that solves \(\dot\varphi=+\nabla V(\varphi)\) costs exactly that. One escape attempt succeeds with probability of order \(e^{-\Delta V/T}\), and is of order \(e^{\Delta V/T}\). That is the exponential in Kramers' law.
Near the bottom of the well the particle forgets its past on a time scale of order one, set by the curvature. So its history is a sequence of nearly independent attempts, each of which reaches the saddle with probability \(\asymp e^{-\Delta V/T}\). The number of attempts before the first success is geometric, and the exit time \(\tau\) is close to exponentially distributed with mean \(\asymp e^{\Delta V/T}\). Freidlin and Wentzell proved \(\lim_{T\to0}T\log\mathbb E[\tau]=\Delta V\), and the exponential law of \(\tau/\mathbb E[\tau]\) is due to Day.
That is as far as large deviations goes. The Eyring–Kramers formula for the one-dimensional overdamped case,
$$\mathbb E[\tau]\;\approx\;\frac{2\pi}{\sqrt{V''(x_-)\,|V''(x_s)|}}\;e^{\Delta V/T},$$
has a prefactor that comes from the curvatures at the bottom and at the saddle. Getting it requires either an asymptotic expansion of the stationary flux or potential theory, and it is invisible to \(\asymp\).
Two remarks on the optimal path. It is the relaxation path run backwards in time, so the system climbs out along the route it would slide down. And the control that produces it is \(u=\dot\varphi-b=2\nabla V\), which cancels the drift and then applies it once more with the sign flipped. The time reversal is , and it goes away when the drift has a rotational part.
A gradient diffusion in its stationary state is reversible: run the film backwards and it has the same law. So the collection of excursions that climb from a level \(a\) to a level \(b\), reversed in time, is statistically identical to the collection that descend from \(b\) to \(a\). This is exact at every temperature. Large deviations adds that as \(T\to0\) both collections concentrate on one curve. In Figure 7 the first statement is why green and blue agree at any \(T\), and the second is why both approach the black curve as \(T\) falls.
Now add a rotation, as in the coda of the Fokker–Planck essay: \(b=-\nabla V+b_\perp\) with \(b_\perp\cdot\nabla V=0\). Expanding the square the same way,
$$S[\varphi]=\frac14\int\big|\dot\varphi-\nabla V-b_\perp\big|^2\mathrm dt+\int\dot\varphi\cdot\nabla V\,\mathrm dt,$$
so the cheapest escape still costs \(\Delta V\), along \(\dot\varphi=\nabla V+b_\perp\). It climbs against the gradient while turning in the same sense as the relaxation path \(\dot\varphi=-\nabla V+b_\perp\). A reversed relaxation path would turn the other way, so the two routes differ. An escape route that is distinct from the reversed relaxation route is an observable signature of a nonequilibrium steady state.
For a drift with neither structure the least cost of reaching \(x\) from the attractor is called the quasi-potential. It solves a Hamilton–Jacobi equation and has no closed form. A good share of the hard problems in this field live there.
Two thousand particles in the left well of \(V(x)=(x^2-1)^2\). Left: every climb from the well bottom to the saddle, with the clock set to zero where it crosses \(x=-0.5\). Right: measured escape rate against \(1/T\), one point per temperature you visit.
Each grey line on the left is one successful climb. Green is their average. Blue is the average of the descents from the saddle back into the well, played backwards. Black is the solution of \(\dot\varphi=+V'(\varphi)\), computed with no noise at all. Green and blue coincide at every temperature, as detailed balance requires. At low temperature they follow the black curve through the steep middle of the climb. Near the saddle the black curve lags, because a noiseless path needs infinite time to reach a point where the drift vanishes, and real particles cover that last stretch on noise. Raise \(T\) and the climbs pull away from the black curve everywhere, since one path no longer dominates.
On the right, move the slider and let the points accumulate. Large deviations predicts the slope of that plot, which is \(\Delta V=1\), and says nothing about its height. The points fall along the line that includes the Eyring–Kramers prefactor, and they start to leave it at the warm end, where nothing is rare any more.
The control essay took a nonlinear Hamilton–Jacobi–Bellman equation, substituted \(V=-\lambda\log\psi\), and obtained a linear one. Fleming noticed in 1978 that the same substitution run the other way proves large deviation estimates. Let \(h(x,t)\) be the probability of some rare event given \(X_t=x\). It is a conditional expectation of the future, so it solves the linear backward equation \(\partial_th+b\cdot\nabla h+T\Delta h=0\). Now \(W=-T\log h\):
With \(h=e^{-W/T}\): \(\partial_th=-\frac{\partial_tW}{T}h\), \(\nabla h=-\frac{\nabla W}{T}h\), and \(\Delta h=\big(-\frac{\Delta W}{T}+\frac{|\nabla W|^2}{T^2}\big)h\). Insert these into the backward equation, divide by \(h\) and multiply by \(-T\):
$$\partial_tW+b\cdot\nabla W+T\,\Delta W-|\nabla W|^2=0.$$
Compare the boxed equation of the control essay, \(-\partial_tV=q+b\cdot\nabla V+T\Delta V-\frac1{2\alpha}|\nabla V|^2\). With \(q=0\) and \(\alpha=\tfrac12\) they coincide. The optimal control there was \(u^{*}=-\nabla V/\alpha\), which here is \(-2\nabla W=2T\nabla\log h\), the drift of the Doob transform.
As \(T\to0\) the solutions \(W^{T}\) converge to the viscosity solution of the first-order equation \(\partial_tW+b\cdot\nabla W-|\nabla W|^2=0\). Its Hamiltonian \(\mathcal H(x,p)=b\cdot p+|p|^2\) has Legendre transform \(\sup_p\{p\cdot v-\mathcal H(x,p)\}=\tfrac14|v-b|^2\) in the velocity variable, which is the Lagrangian of the Freidlin–Wentzell action. One more Legendre pair, this time between the Hamiltonian and Lagrangian descriptions of the same control problem.
$$-\,\partial_tW\;=\;b\cdot\nabla W-|\nabla W|^2+T\,\Delta W.$$
This is the Hamilton–Jacobi–Bellman equation of the control essay with \(\alpha=\tfrac12\), and the temperature now appears only as the coefficient of the Laplacian. As \(T\to0\) that term drops out. What is left is a first-order Hamilton–Jacobi equation whose solution is the least action needed to reach the event from \((x,t)\). So \(h\asymp e^{-W/T}\) with \(W\) a value function. In the language of differential equations, a large deviation principle is the vanishing-viscosity limit of a Bellman equation.
The same substitution says what the process does on its way to the rare event. Conditioning on the event is a Doob transform, which adds the drift \(2T\nabla\log h=-2\nabla W\). That is the optimal feedback control. A diffusion conditioned on a rare event behaves like a diffusion steered toward it at least cost. The last figure of the control essay, where a crowd selected by rejection and a crowd under control had the same histogram at every time, showed this at finite temperature.
Here are four places where the material above is in daily use, mostly without the name.
Fix a state. You have a prior policy \(\pi_0\) over actions and estimates \(Q(a)\) of how good each action is. A cautious update maximizes expected \(Q\) while paying for every nat it moves away from \(\pi_0\):
$$\max_{\pi}\Big\{\mathbb E_\pi[Q]-\eta\,\mathrm{KL}(\pi\,\|\,\pi_0)\Big\}.$$
By the Gibbs variational principle the maximizer is \(\pi\propto\pi_0\,e^{Q/\eta}\) and the maximum is \(\eta\log\mathbb E_{\pi_0}[e^{Q/\eta}]\). With \(\pi_0\) uniform these are a softmax and a log-sum-exp, and iterating over states gives the soft Bellman equation that closed the control essay. With \(\pi_0\) the previous policy they are the update at the centre of relative entropy policy search and of MPO. TRPO imposes the same KL constraint and solves it approximately. Soft actor-critic, maximum-entropy RL and KL control are this computation with different choices of \(\pi_0\) and different rules for setting \(\eta\).
The title equation has a twin with the signs reversed:
$$T\log\mathbb E_\mu\big[e^{C/T}\big]\;=\;\sup_{\nu}\Big\{\mathbb E_\nu[C]-T\,\mathrm{KL}(\nu\,\|\,\mu)\Big\}.$$
Read both with \(C\) a cost and \(\mu\) the distribution of the randomness you face. In the title equation the infimum hands the choice of \(\nu\) to whoever is minimizing the cost. The agent bends the noise in its own favour and pays \(T\) per nat for doing so. In the twin the supremum hands \(\nu\) to an adversary, who bends the noise against the agent at the same tariff. The first is the objective of control as inference. The second is risk-sensitive control with the entropic risk measure, and by this formula it equals robust control against every model within a KL budget of the nominal one. That equivalence goes back to Jacobson in the 1970s, and Dupuis, James and Petersen made it precise for diffusions.
shows the difference in one line: the first objective is \(\mathbb E[C]-\mathrm{Var}(C)/2T+\dots\) and the second is \(\mathbb E[C]+\mathrm{Var}(C)/2T+\dots\). The coda of the control essay called its agent mildly risk-seeking and left it at that. The variational form says where the optimism comes from. The agent's objective treats the noise as something it gets to choose. When the KL term is a real control cost, as in that essay's setup where steering and noise enter through the same channel, that is correct accounting. When you take a problem whose randomness belongs to the environment and convert costs into log-likelihoods, you have given the agent a say over the weather.
The function \(s\mapsto\log\mathbb E[e^{sC}]\) is the cumulant generating function of \(C\): \(s\,\mathbb E[C]+\frac{s^2}{2}\mathrm{Var}(C)+\dots\). Hence
$$-T\log\mathbb E\big[e^{-C/T}\big]=\mathbb E[C]-\frac{\mathrm{Var}(C)}{2T}+\dots,\qquad T\log\mathbb E\big[e^{C/T}\big]=\mathbb E[C]+\frac{\mathrm{Var}(C)}{2T}+\dots$$
Of two plans with equal expected cost the first criterion prefers the riskier and the second prefers the safer. As \(T\to\infty\) both reduce to the expected cost. As \(T\to0\) the first tends to the best case of \(C\) and the second to the worst case.
The robust reading of the second: for any model \(\nu\) with \(\mathrm{KL}(\nu\|\mu)\le r\), the formula gives \(\mathbb E_\nu[C]\le T\log\mathbb E_\mu[e^{C/T}]+T\,r\). A controller that keeps the entropic risk small under the nominal model has bounded expected cost under every model in a KL ball around it. Hansen and Sargent made the same idea a programme in economics.
Suppose you need the probability of an event of probability \(10^{-9}\), a failure mode or a barrier crossing. Plain Monte Carlo needs billions of runs to see it once. Importance sampling draws from a different law \(Q\) and reweights each sample by \(\mathrm dP/\mathrm dQ\). The best possible \(Q\) is the original law conditioned on the event, which gives an estimator with zero variance and requires knowing the answer beforehand. Large deviations says what that conditional law looks like: a tilt, for sums, and an optimally controlled process, for diffusions. So one approximates the tilt.
Rubinstein's cross-entropy method, from 1997, does it by iteration. Sample from a parametric \(Q\), keep the elite fraction of samples closest to the event, refit \(Q\) to the elites by maximum likelihood, which is a KL projection, and repeat. It was invented for estimating rare-event probabilities in stochastic networks. It turned out to be a decent black-box optimizer as well, since an optimum is a rare event under any broad sampling distribution, and that is the form in which RL uses it, for policy search and for planning inside learned models. MPPI, from the third figure of the control essay, is the same loop with exponential weights in place of an elite cutoff. The collapse of effective sample size in that figure is the rare-event problem. The standard remedy, sampling around the previous plan in place of the passive dynamics, is importance sampling from an approximate tilt.
A bandit algorithm has to decide how many pulls to spend on an arm that looks bad. Lai and Robbins answered with a lower bound in 1985. For Bernoulli arms, any algorithm that does well on every bandit must pull a suboptimal arm with mean \(p_a\) at least
$$\frac{\log t}{\mathrm{KL}\big(\mathrm{Ber}(p_a)\,\|\,\mathrm{Ber}(p^{*})\big)}$$
times in \(t\) rounds, asymptotically, where \(p^{*}\) is the best arm's mean. is the lower-bound half of Cramér's theorem: change the measure to a world in which that arm is the best one, and note that an algorithm cannot do well in both worlds unless it has enough samples of the arm to tell them apart.
Call an algorithm consistent if on every bandit its expected number of suboptimal pulls up to time \(t\) is \(o(t^{\epsilon})\) for every \(\epsilon>0\). Fix a bandit, and a suboptimal arm \(a\) with mean \(p_a\). Build a second bandit, identical except that arm \(a\) has mean \(p'\) slightly above \(p^{*}\), so that in the second world \(a\) is the best arm.
Let \(N_a(t)\) be the number of pulls of \(a\). The log-likelihood ratio between the two worlds, given what the algorithm has seen, is a sum of \(N_a(t)\) terms each with mean \(\mathrm{KL}(\mathrm{Ber}(p_a)\|\mathrm{Ber}(p'))\). If \(N_a(t)\) were much smaller than \(\log t/\mathrm{KL}\), the likelihood ratio would be smaller than \(t\), and the event "arm \(a\) was pulled rarely", which has probability near one in the first world, would have probability at least about \(1/t\) in the second. In the second world, pulling \(a\) rarely means regret of order \(t\) on that event, which contradicts consistency. Letting \(p'\downarrow p^{*}\) gives the bound.
It is the tilting argument of Part I. A change of measure makes an event typical, and the likelihood ratio is the price. The only new ingredient is that the number of samples is chosen by the algorithm.
KL-UCB, due to Garivier and Cappé (2011), turns the bound into an algorithm. After \(n\) pulls of an arm with empirical mean \(\hat p\), its index is the largest mean that the data cannot yet rule out at level \(1/t\):
$$U\;=\;\max\Big\{q\;:\;n\,\mathrm{KL}\big(\mathrm{Ber}(\hat p)\,\|\,\mathrm{Ber}(q)\big)\le\log t\Big\}.$$
The quantity \(n\,\mathrm{KL}(\hat p\|q)\) is the Sanov exponent for an arm of true mean \(q\) to have produced the average \(\hat p\). The usual UCB index is the same recipe with KL replaced by its lower bound \(2(\hat p-q)^2\) from Pinsker's inequality, which is what Hoeffding's inequality uses. Near \(p=\tfrac12\) the two rate functions are close. Near 0 or 1 the parabola badly underestimates how fast a Bernoulli average concentrates, the confidence intervals come out too wide, and the algorithm explores more than it has to.
Three Bernoulli arms with means \(m\), \(m-0.1\), \(m-0.2\). Left: one run, with both upper confidence bounds computed from the same data. Right: regret averaged over 80 runs of each algorithm, against \(\log t\).
Regret is plotted against \(\log t\), so logarithmic regret shows as a straight line. The dashed lines are asymptotic slopes: the Lai–Robbins constant \(\sum_a\Delta_a/\mathrm{KL}(p_a\|p^{*})\) for the KL index, and the same sum with \(2\Delta_a^2\) in place of the KL divergence for the Hoeffding index, where \(\Delta_a=p^{*}-p_a\). Slide the best arm's mean toward 1 and the two separate. Put it near \(\tfrac12\) and they nearly coincide, because there the parabola is a good approximation to the rate function.
Here is what the theory does not give you, in the order in which it tends to bite.
Only the exponent. Every statement above is at the level of \(\asymp\). The prefactor in Kramers' law, the \(\sqrt n\) in the coin and the height of the line in Figure 7 are all absent from the rate function. For moderate \(n\) or moderate \(1/T\) the missing factor can matter more than the exponent does, and getting it takes sharper tools.
Light tails. Cramér's theorem needs \(\Lambda\) finite near zero. For heavy-tailed variables \(\Lambda(\theta)=\infty\) for every \(\theta>0\), the rate function is zero on that side, and the theory returns nothing. What happens there is the . A sum of heavy-tailed variables is large because one of them is enormous. Under a tilt every sample shifts a little. Under a heavy tail one sample does everything and the others are ordinary. Which regime you are in depends on the tail, and it matters for anything involving returns, insurance claims or file sizes.
For i.i.d. variables with regularly varying tails, say \(\mathbb P(X>y)\sim c\,y^{-\alpha}\) with \(\alpha>1\), and \(x\) above the mean \(m\),
$$\mathbb P(S_n\ge nx)\;\sim\;n\;\mathbb P\big(X_1\ge n(x-m)\big).$$
The right side is the probability that at least one sample alone covers the whole excess. It decays like a power of \(n\). Conditional on the event, \(n-1\) of the samples look like draws from the original law and one is of size about \(n(x-m)\). There is no conditional limit theorem toward a tilt and no maximum entropy description. Results of this type go back to Nagaev and to Heyde.
Convexity. The Legendre route sees only the convex hull of a rate function, as the magnet preset showed. Nonconvex rate functions are common once variables interact, and they have to be found by other means, usually the contraction principle or Varadhan's lemma applied to something that is convex one level up.
Independence. Parts I to III assumed independent samples. For the long-time averages of a Markov process there is still a large deviation principle, and is itself given by a variational formula. That theory is the subject of the four papers by Donsker and Varadhan whose names are on the lemma in Part II. I have left it out.
Let \(X_t\) be an ergodic Markov process with generator \(\mathcal L\), and let \(L_t=\frac1t\int_0^t\delta_{X_s}\mathrm ds\) be the fraction of time it spends in each region up to time \(t\). Then \(L_t\) satisfies a large deviation principle with speed \(t\) and rate function
$$I(\nu)\;=\;-\inf_{u>0}\int\frac{\mathcal Lu}{u}\,\mathrm d\nu.$$
The analogue of the title equation is
$$\lim_{t\to\infty}\frac1t\log\mathbb E\Big[e^{\int_0^tf(X_s)\,\mathrm ds}\Big]\;=\;\sup_{\nu}\Big\{\int f\,\mathrm d\nu-I(\nu)\Big\},$$
and the left side is the principal eigenvalue of the operator \(\mathcal L+f\). This is the long-time limit of the Feynman–Kac formula from the control essay. For a reversible diffusion \(I(\nu)\) reduces to a Dirichlet form of \(\sqrt{\mathrm d\nu/\mathrm d\rho_\infty}\), and the formula becomes the Rayleigh–Ritz principle for the ground state of a Schrödinger operator. It is the entry point to ergodic and risk-sensitive control, where the eigenvalue plays the part of the optimal long-run cost.
Two loose ends from the other essays close here. Part III of the Fokker–Planck essay showed that diffusion is the steepest descent of the free energy in the Wasserstein metric, and offered no reason why that metric and that functional should belong together. Adams, Dirr, Peletier and Zimmer gave one in 2011. Take \(n\) independent Brownian particles and ask for the probability that their empirical measure moves from \(\rho_0\) to \(\rho\) in a short time \(\tau\). As \(\tau\to0\), the rate functional of that event agrees, up to a constant factor, with the functional that the JKO scheme minimizes. So a JKO step is the most likely thing for the particle system to do, and the JKO functional measures the improbability of its doing anything else. And Schrödinger's problem, from the last part of the optimal transport essay, is Sanov's theorem for whole paths followed by the contraction principle onto the two endpoints.
If I had to compress the essay into a sentence, it would be that a probability on the exponential scale is an optimal cost, and the optimizer is how the event happens. The Gibbs variational principle is the case in which this holds exactly, with no limit.