Relative Entropy as a Rate Function and the Donsker-Varadhan Variational Formula

Intuition Beginner

Suppose you have two ways of generating random outcomes — call them the reference recipe and the target recipe. The reference might be a fair coin; the target a coin biased toward heads. Relative entropy is a single number that measures how surprised the reference would be to see data that actually came from the target. If the two recipes agree, the surprise is zero. The more they differ, the larger the number grows.

Why phrase it as surprise rather than just "distance"? Because the natural way to compare two probability recipes is to watch how often each outcome shows up and compare the two frequencies outcome by outcome, weighting by how often the target actually produces that outcome. Each outcome contributes the logarithm of the ratio of the two probabilities, and you average those log-ratios using the target's own weights. That averaged log-ratio is the relative entropy, written $H$ of target against reference.

This number is the natural "cost" in the theory of rare events. If you run the reference recipe many times and ask how unlikely it is that the observed frequencies look like the target instead, the answer decays exponentially, and the exponent is exactly the relative entropy. Cheap-to-fake targets sit close to the reference and have small relative entropy; targets that demand an extreme coincidence have large relative entropy. That is why it serves as a rate function: it is the price, per observation, of a rare statistical mirage.

Two facts make it well behaved. First, it is never negative, and it is zero only when the two recipes match — a fact that follows from the curvature of the logarithm. Second, even though it is built from a ratio that looks fragile, it can be rewritten as a clean maximisation over "test functions," which is what makes it tractable. And it controls a more familiar notion of distance: a small relative entropy forces the two recipes to assign nearly equal probabilities to every event.

Visual Beginner

Figure: two bar charts side by side over the same four outcomes. The left chart is the reference distribution (four roughly equal bars); the right chart is the target distribution (one tall bar, three short ones). Below each pair of bars is the log-ratio of target-to-reference height; these log-ratios are averaged with the target's weights to give the single number H. A second small panel plots the curve $t\mapsto t\log t$, convex and dipping below zero between $0$ and $1$, the curvature that forces H to be non-negative.

   reference p              target q            log-ratio  weight (q)
   |                        |  ___              log(q/p)   used to
   | _  _  _  _             | |   |             per bar    average
   || || || ||             | |   | _  _  _      ---------------------
   ----------------         ------------------   H = sum  q * log(q/p)
    a  b  c  d               a  b  c  d                >= 0,  =0 iff p=q

   curvature that forces H >= 0:   t log t
        \           /              dips below 0 on (0,1),
         \_________/               convex everywhere

Worked example Beginner

Take a reference fair coin and a biased target coin, and compute the relative entropy of target against reference.

Step 1. Write down the two recipes. The reference $p$ assigns heads and tails each probability $1/2$. The target $q$ assigns heads probability $3/4$ and tails probability $1/4$.

Step 2. Form the log-ratio at each outcome. For heads, the ratio is $(3/4)/(1/2)=3/2$, with logarithm (natural log) $\log (3/2)\approx 0.405$. For tails, the ratio is $(1/4)/(1/2)=1/2$, with logarithm $\log (1/2)\approx -0.693$.

Step 3. Average using the target's weights. The target produces heads three-quarters of the time and tails one-quarter, so weight the two log-ratios by $3/4$ and $1/4$:

$$H=\frac{3}{4}\log \frac{3}{2}+\frac{1}{4}\log \frac{1}{2}\approx \frac{3}{4}(0.405)+\frac{1}{4}(-0.693)\approx 0.304-0.173=\mathrm{0.131.}$$

Step 4. Sanity check the sign. The number $0.131$ is positive, as it must be, and it would have come out exactly zero had the target equalled the reference. The negative contribution from tails did not overpower the positive contribution from heads, because the averaging uses the target's weights, which favour the heads term.

What this tells us. The single number $0.131$ says that if you flip a fair coin a great many times, the chance the observed heads-frequency mimics the $3/4$-biased coin decays like $e^{-0.131n}$. The cost per flip of this statistical coincidence is the relative entropy. A more extreme target would have produced a larger number and a faster decay.

Check your understanding Beginner

Formal definition Intermediate+

Let $(\Omega ,\mathcal{F})$ be a measurable space and let $\mu ,\nu$ be probability measures on it. Recall from 02.07.08 that $\nu$ is absolutely continuous with respect to $\mu$, written $\nu \ll \mu$, when every $\mu$-null set is $\nu$-null, in which case the Radon-Nikodym derivative $d\nu /d\mu$ exists as a non-negative $\mu$-integrable function.

Definition (relative entropy). The relative entropy (Kullback-Leibler divergence) of $\nu$ with respect to $\mu$ is

$$\boxed{H(\nu \Vert \mu ):=\{\begin{array}{ll}{\int }_{\Omega }\log \frac{d\nu }{d\mu }d\nu ={\int }_{\Omega }\frac{d\nu }{d\mu }\log \frac{d\nu }{d\mu }d\mu ,& \nu \ll \mu ,\\ +\infty ,& \nu /\ll \mu .\end{array}}$$

The two integrals coincide because $d\nu =(d\nu /d\mu )d\mu$. Writing $\phi (t)=t\log t$ (with $\phi (0):=0$) and $f=d\nu /d\mu$, the relative entropy is $H(\nu \Vert \mu )={\int }_{\Omega }\phi (f)d\mu$, the $\mu$-integral of the strictly convex function $\phi$ applied to the density. The integrand $f\log f$ is bounded below by the integrable function $f-1$ (since $\log t\ge 1-1/t$), so the integral is well-defined in $(-\infty ,+\infty ]$; non-negativity (Theorem below) sharpens this to $[0,+\infty ]$.

Definition (total variation). The total variation distance between $\mu$ and $\nu$ is

$$\Vert \nu -\mu {\Vert }_{\mathrm{TV}}:=\underset{A\in \mathcal{F}}{\sup }|\nu (A)-\mu (A)|=\frac{1}{2}{\int }_{\Omega }|\frac{d\nu }{d\lambda }-\frac{d\mu }{d\lambda }|d\lambda ,$$

where $\lambda$ is any common dominating measure (e.g. $\lambda =\mu +\nu$); the value is independent of the choice of $\lambda$.

Definition (Donsker-Varadhan functional). For a bounded measurable function $g:\Omega \to \mathbb{R}$ write the log-moment-generating functional ${\Lambda }_{\mu }(g):=\log {\int }_{\Omega }{e}^{g}d\mu$. The Donsker-Varadhan functional of $\nu$ is

$$J_{\mu }(\nu ):=\underset{g}{\sup }\{{\int }_{\Omega }gd\nu -\log {\int }_{\Omega }{e}^{g}d\mu \},$$

the supremum taken over bounded measurable $g$. The central theorem is that $J_{\mu }=H(\cdot \Vert \mu )$. This exhibits $H(\cdot \Vert \mu )$ as the Legendre-Fenchel conjugate 37.07.03 of the convex functional $g\mapsto {\Lambda }_{\mu }(g)$ under the pairing $(g,\nu )\mapsto \int gd\nu$ between bounded measurable functions and probability measures.

Counterexamples to common slips

• Relative entropy is not a metric. It fails symmetry, $H(\nu \Vert \mu )\ne H(\mu \Vert \nu )$ in general, and fails the triangle inequality. For Bernoulli$(1)$ against Bernoulli$(1/2)$ the divergence is $\log 2$, while the reverse, Bernoulli$(1/2)$ against Bernoulli$(1)$, is $+\infty$ because $\nu =\mathrm{Ber}(1/2)/\ll \mathrm{Ber}(1)$. The asymmetry is structural, not a normalisation artifact.
• Finiteness needs absolute continuity, not just a common support. If $\nu$ places mass where $\mu$ has density zero, then $\nu /\ll \mu$ and $H(\nu \Vert \mu )=+\infty$, even if $\mu$ and $\nu$ are mutually absolutely continuous on the rest of the space. A single point of leakage forces the infinite value.
• The supremum in Donsker-Varadhan is over $g$, not over $\nu$. The variational formula computes $H(\nu \Vert \mu )$ for fixed $\nu$ by maximising over test functions $g$; the optimiser is the log-density $g_{\star }=\log (d\nu /d\mu )$ (when bounded), at which $\int g_{\star }d\nu -{\Lambda }_{\mu }(g_{\star })=H(\nu \Vert \mu )$. Reading the formula as a maximisation over measures inverts its meaning.

Key theorem with proof Intermediate+

We prove the two structural pillars: non-negativity via Gibbs' inequality, and the Donsker-Varadhan variational identity, the latter realising $H(\cdot \Vert \mu )$ as a Fenchel conjugate in the sense of 37.07.03.

Theorem (Gibbs' inequality and the Donsker-Varadhan formula). Let $\mu ,\nu$ be probability measures on $(\Omega ,\mathcal{F})$.

(i) (Gibbs' inequality.) $H(\nu \Vert \mu )\ge 0$, with equality if and only if $\nu =\mu$.

(ii) (Donsker-Varadhan.) For bounded measurable $g$ one has the duality

$$H(\nu \Vert \mu )=\underset{g}{\sup }\{{\int }_{\Omega }gd\nu -\log {\int }_{\Omega }{e}^{g}d\mu \},$$

and dually, for every bounded measurable $g$,

$$\log {\int }_{\Omega }{e}^{g}d\mu =\underset{\nu }{\sup }\{{\int }_{\Omega }gd\nu -H(\nu \Vert \mu )\},$$

the supremum over probability measures $\nu$.

Proof of (i). If $\nu /\ll \mu$ the value is $+\infty \ge 0$, so assume $\nu \ll \mu$ with density $f=d\nu /d\mu$. The function $\phi (t)=t\log t$ is strictly convex on $[0,\infty )$ with $\phi (1)=0$ and supporting line $t-1$ at $t=1$, so $\phi (t)\ge t-1$ with equality only at $t=1$. Integrating against $\mu$,

$$H(\nu \Vert \mu )={\int }_{\Omega }\phi (f)d\mu \ge {\int }_{\Omega }(f-1)d\mu =\nu (\Omega )-\mu (\Omega )=1-1=0.$$

Equality in the integrated inequality forces $\phi (f)=f-1$ $\mu$-a.e., hence $f=1$ $\mu$-a.e., i.e. $\nu =\mu$. (Equivalently, by Jensen's inequality applied to the convex $\phi$ and the probability measure $\mu$: $\int \phi (f)d\mu \ge \phi (\int fd\mu )=\phi (1)=0$, with equality iff $f$ is $\mu$-a.e. constant, forcing $f\equiv 1$.) $\square$

Proof of (ii). Upper bound $H\ge \int gd\nu -{\Lambda }_{\mu }(g)$. Assume $\nu \ll \mu$; otherwise $H=+\infty$ dominates the right side at once. Fix bounded measurable $g$ and define the tilted probability measure ${\mu }_g$ by $d{\mu }_g=e^{g-{\Lambda }_{\mu }(g)}d\mu$, a probability measure since $\int e^{g-{\Lambda }_{\mu }(g)}d\mu =1$. Because $g$ is bounded, ${\mu }_g$ is mutually absolutely continuous with $\mu$, and $\nu \ll \mu \ll {\mu }_g$, so the chain rule for Radon-Nikodym derivatives 02.07.08 gives $\frac{d\nu }{d{\mu }_g}=\frac{d\nu }{d\mu }{e}^{{\Lambda }_{\mu }(g)-g}$. Then

$$H(\nu \Vert {\mu }_g)=\int \log \frac{d\nu }{d{\mu }_g}d\nu =\int (\log \frac{d\nu }{d\mu }-g+{\Lambda }_{\mu }(g))d\nu =H(\nu \Vert \mu )-\int gd\nu +{\Lambda }_{\mu }(g).$$

By part (i), $H(\nu \Vert {\mu }_g)\ge 0$, which rearranges to $H(\nu \Vert \mu )\ge \int gd\nu -{\Lambda }_{\mu }(g)$. Taking the supremum over $g$ gives $H(\nu \Vert \mu )\ge J_{\mu }(\nu )$.

Sharpness $H\le J_{\mu }(\nu )$. It remains to exhibit $g$'s realising the supremum. Suppose first $H(\nu \Vert \mu )<\infty$ with $f=d\nu /d\mu$, and take $g_{\star }=\log f$. The computation above with $g=g_{\star }$ gives $H(\nu \Vert {\mu }_{g_{\star }})=0$, i.e. $\int g_{\star }d\nu -{\Lambda }_{\mu }(g_{\star })=H(\nu \Vert \mu )$, and ${\Lambda }_{\mu }(g_{\star })=\log \int fd\mu =\log 1=0$. When $g_{\star }$ is unbounded, truncate: $g_n=(\log f)\wedge n$ on $\{f\ge e^{-n}\}$ and $g_n=-n$ elsewhere are bounded, and monotone/dominated convergence 02.07.06 gives $\int g_{n}d\nu -{\Lambda }_{\mu }(g_n)\to H(\nu \Vert \mu )$. So the supremum equals $H(\nu \Vert \mu )$. If $H(\nu \Vert \mu )=+\infty$, either $\nu /\ll \mu$ — then choosing $g$ large on a $\nu$-positive $\mu$-null set drives $\int gd\nu -{\Lambda }_{\mu }(g)\to \infty$ — or the log-density is non-integrable, where the same truncation yields an unbounded supremum. The dual identity is the biconjugation ${\Lambda }_{\mu }=({\Lambda }_{\mu }{)}^{\ast \ast }$ of 37.07.03 applied to the convex lsc functional ${\Lambda }_{\mu }$, whose conjugate is $H(\cdot \Vert \mu )$ on probability measures and $+\infty$ off them. $\square$

Bridge. This theorem builds toward Sanov's theorem and the entire empirical-measure large-deviations theory, where $H(\cdot \Vert \mu )$ appears again in the role the conjugate ${\Lambda }^{\ast }$ played for sample means in 37.07.03. This is exactly the Fenchel duality of that unit, now staged in infinite dimensions: $H(\cdot \Vert \mu )$ is dual to the log-moment functional ${\Lambda }_{\mu }(g)=\log \int e^{g}d\mu$ under the pairing $⟨g,\nu ⟩=\int gd\nu$, so relative entropy generalises the cumulant-conjugate rate function from ${\mathbb{R}}^d$-valued means to measure-valued empirical laws. The foundational reason $H$ is a good rate function is that it is a Fenchel conjugate of a convex functional, inheriting non-negativity from ${\Lambda }_{\mu }(0)=0$ exactly as ${\Lambda }^{\ast }$ did. Putting these together, the optimal test function $g_{\star }=\log (d\nu /d\mu )$ plays the role of the optimal exponential tilt ${\lambda }_x$ of Cramér's theorem, and the tilted measure ${\mu }_g$ is the infinite-dimensional analogue of the exponentially tilted law.

Exercises Intermediate+

Advanced results Master

Joint convexity and lower semicontinuity

The map $(\nu ,\mu )\mapsto H(\nu \Vert \mu )$ is jointly convex: for $\theta \in [0,1]$ and probability measures ${\nu }_0,{\nu }_1,{\mu }_0,{\mu }_1$,

$$H(\theta {\nu }_1+(1-\theta ){\nu }_0\Vert \theta {\mu }_1+(1-\theta ){\mu }_0)\le \theta H({\nu }_1\Vert {\mu }_1)+(1-\theta )H({\nu }_0\Vert {\mu }_0).$$

This is the log-sum inequality of Csiszár ^{[Csiszár 1967]}: for non-negative $a_i,b_i$, ${\sum }_i{a}_i\log (a_i/b_i)\ge ({\sum }_i{a}_i)\log ({\sum }_i{a}_i/{\sum }_i{b}_i)$, applied to the perspective function $(a,b)\mapsto a\log (a/b)$, which is jointly convex on $(0,\infty {)}^2$ as the perspective of the convex $t\mapsto \log t^{-1}$. Joint lower semicontinuity in the weak topology of measures follows from the Donsker-Varadhan representation: $H(\nu \Vert \mu )={\sup }_g\{\int gd\nu -\log \int e^{g}d\mu \}$ exhibits $H$ as a supremum, over bounded continuous $g$, of functionals jointly continuous in $(\nu ,\mu )$, and a supremum of lsc functions is lsc. Joint lower semicontinuity is precisely what makes $H(\cdot \Vert \mu )$ a good rate function on the space of probability measures with compact sublevel sets when $\Omega$ is Polish ^{[Dembo & Zeitouni §6.2]}.

Sanov's theorem: relative entropy as the empirical-measure rate function

Let $X_1,X_2,\dots$ be i.i.d. with law $\mu$ on a Polish space, and let $L_n=\frac{1}{n}{\sum }_{i=1}^n{\delta }_{X_i}$ be the empirical measure. Sanov's theorem ^{[Sanov 1957]} states that $(L_n)$ satisfies a large deviation principle on the space ${\mathcal{M}}_1(\Omega )$ of probability measures, equipped with the weak topology, with good rate function $H(\cdot \Vert \mu )$: for measurable $\Gamma \subseteq {\mathcal{M}}_1(\Omega )$,

$$-\underset{\nu \in {\Gamma }^{\circ }}{\inf }H(\nu \Vert \mu )\le \underset{n}{\mathrm{liminf}}\frac{1}{n}\log \mathbb{P}(L_n\in \Gamma )\le \underset{n}{\mathrm{limsup}}\frac{1}{n}\log \mathbb{P}(L_n\in \Gamma )\le -\underset{\nu \in \bar{\Gamma }}{\inf }H(\nu \Vert \mu ).$$

The upper bound is a tilting/Chernoff argument: for bounded $g$, $\mathbb{E}{e}^{n\int gd{L}_n}=(\int e^{g}d\mu {)}^n$, and optimising $\int gd{L}_n-{\Lambda }_{\mu }(g)$ over $g$ via Donsker-Varadhan produces $H$. This is the infinite-dimensional twin of Cramér's theorem 37.07.03: empirical means are replaced by empirical measures, the cumulant generating function $\Lambda (\lambda )$ by the functional ${\Lambda }_{\mu }(g)$, and the conjugate ${\Lambda }^{\ast }$ by $H(\cdot \Vert \mu )$.

The contraction principle recovers Cramér

Applying the contraction principle of 37.07.03 to Sanov's theorem through the continuous map $\nu \mapsto \int xd\nu (x)$ (the mean functional) recovers Cramér's rate function as a constrained relative-entropy minimisation:

$${\Lambda }^{\ast }(a)=\inf \{H(\nu \Vert \mu ):\int xd\nu (x)=a\}.$$

The minimiser is the exponentially tilted law $d{\nu }_{\star }=e^{{\lambda }_{a}x-\Lambda ({\lambda }_a)}d\mu$ at the tilt ${\lambda }_a$ solving $\nabla \Lambda ({\lambda }_a)=a$ — exactly the Cramér optimiser of 37.07.03 — and the identity ${\Lambda }^{\ast }(a)=H({\nu }_{\star }\Vert \mu )$ identifies the scalar rate function as the relative entropy of the optimally tilted measure. This is the precise sense in which Sanov contains Cramér.

Stein's lemma and the operational meaning

In binary hypothesis testing of $\mu$ against $\nu$ with $n$ i.i.d. samples, Stein's lemma ^{[Cover & Thomas §11.6]} shows the best achievable type-II error exponent, at fixed type-I error, is exactly $H(\nu \Vert \mu )$. Relative entropy is therefore not merely a convenient rate function but the operational rate of distinguishability: $e^{-nH(\nu \Vert \mu )}$ is the optimal exponential rate at which a likelihood-ratio test drives the missed-detection probability to zero. The Donsker-Varadhan optimiser $g_{\star }=\log (d\nu /d\mu )$ is precisely the log-likelihood-ratio statistic of the Neyman-Pearson test.

Synthesis. Relative entropy is exactly the Fenchel conjugate of the log-moment functional ${\Lambda }_{\mu }(g)=\log \int e^{g}d\mu$, so it generalises the cumulant-conjugate rate function ${\Lambda }^{\ast }$ of 37.07.03 from ${\mathbb{R}}^d$-valued means to measure-valued empirical laws, and this is exactly why Sanov's theorem stands to empirical measures as Cramér's theorem stands to empirical means. The central insight is that the Donsker-Varadhan duality $H(\nu \Vert \mu )={\sup }_g\{\int gd\nu -{\Lambda }_{\mu }(g)\}$ is the infinite-dimensional Fenchel-Young pairing, with optimal test function $g_{\star }=\log (d\nu /d\mu )$ playing the role of the optimal exponential tilt and the tilted measure ${\mu }_g$ the role of the exponentially tilted law. The foundational reason $H$ is a good rate function — non-negative by Gibbs, jointly convex by the log-sum inequality, jointly lsc and compact-sublevelled by the variational representation — is that it is a convex conjugate, inheriting every structural property from ${\Lambda }_{\mu }$. Putting these together with Pinsker's inequality, which makes relative-entropy convergence dominate total-variation convergence, and with Stein's lemma, which gives $H$ its operational testing meaning, the bridge is biconjugation 37.07.03: $H(\cdot \Vert \mu )$ and ${\Lambda }_{\mu }$ are a dual pair, and the contraction principle through the mean functional appears again in recovering Cramér from Sanov as a constrained entropy minimisation.

Full proof set Master

Proposition 1 (Donsker-Varadhan as a Fenchel conjugate). Let $\mu$ be a probability measure on $(\Omega ,\mathcal{F})$. On the space of probability measures, $H(\cdot \Vert \mu )$ is the convex conjugate of ${\Lambda }_{\mu }(g)=\log \int e^{g}d\mu$ under the pairing $⟨g,\nu ⟩=\int gd\nu$, and ${\Lambda }_{\mu }$ is its biconjugate.

Proof. The Key theorem part (ii) gives $H(\nu \Vert \mu )={\sup }_g\{⟨g,\nu ⟩-{\Lambda }_{\mu }(g)\}={\Lambda }_{\mu }^{\ast }(\nu )$, the conjugate evaluated at $\nu$, and extends it by $+\infty$ to signed measures of total mass $\ne 1$ (taking $g$ constant drives the supremum to $+\infty$ unless $\nu (\Omega )=1$). The functional ${\Lambda }_{\mu }$ is convex by Hölder — for $\theta \in [0,1]$, $\int e^{\theta g_1+(1-\theta )g_2}d\mu \le (\int e^{g_1}d\mu {)}^{\theta }(\int e^{g_2}d\mu {)}^{1-\theta }$, then take logs — and lsc, so by Fenchel-Moreau 37.07.03, ${\Lambda }_{\mu }={\Lambda }_{\mu }^{\ast \ast }=(H(\cdot \Vert \mu ){)}^{\ast }$, the second dual identity of the Key theorem. $\square$

Proposition 2 (joint convexity via the log-sum inequality). For probability measures ${\nu }_0,{\nu }_1,{\mu }_0,{\mu }_1$ and $\theta \in [0,1]$, with ${\nu }_{\theta }=\theta {\nu }_1+(1-\theta ){\nu }_0$ and ${\mu }_{\theta }=\theta {\mu }_1+(1-\theta ){\mu }_0$, $H({\nu }_{\theta }\Vert {\mu }_{\theta })\le \theta H({\nu }_1\Vert {\mu }_1)+(1-\theta )H({\nu }_0\Vert {\mu }_0)$.

Proof. The perspective function $p(a,b)=a\log (a/b)$ on $(0,\infty {)}^2$ (with $p(0,b)=0$, $p(a,0)=+\infty$ for $a>0$) is jointly convex: it is the perspective $p(a,b)=b\varphi (a/b)$ of the convex $\varphi (t)=t\log t$, and the perspective of a convex function is jointly convex ^{[Csiszár 1967]}. Directly, the Hessian \nabla^2 p = \begin{psmallmatrix} 1/a & -1/b \\ -1/b & a/b^2 \end{psmallmatrix} has non-negative trace and determinant $\frac{1}{a}\cdot \frac{a}{b^2}-\frac{1}{b^2}=0$, so it is positive semidefinite. Choose a common dominating measure $\lambda$ with densities $f_i=d{\nu }_i/d\lambda$, $g_i=d{\mu }_i/d\lambda$. Then $H({\nu }_i\Vert {\mu }_i)=\int p(f_i,g_i)d\lambda$, and the densities of the mixtures are $f_{\theta }=\theta f_1+(1-\theta )f_0$, $g_{\theta }=\theta g_1+(1-\theta )g_0$. Pointwise joint convexity of $p$ gives $p(f_{\theta },g_{\theta })\le \theta p(f_1,g_1)+(1-\theta )p(f_0,g_0)$; integrate against $\lambda$. $\square$

Proposition 3 (Pinsker's inequality). For probability measures $\mu ,\nu$, $\Vert \nu -\mu {\Vert }_{\mathrm{TV}}\le \sqrt{\frac{1}{2}H(\nu \Vert \mu )}$.

Proof. If $\nu /\ll \mu$ the right side is $+\infty$ and there is nothing to prove, so assume $\nu \ll \mu$. The binary case $d(q\Vert p)\ge 2(q-p{)}^2$ is Exercise 6: with $\psi (q)=d(q\Vert p)-2(q-p{)}^2$ one has $\psi (p)={\psi }^{\prime }(p)=0$ and ${\psi }^{\prime \prime }(q)=\frac{1}{q(1-q)}-4\ge 0$ since $q(1-q)\le \frac{1}{4}$, so $\psi \ge 0$. For the general case, fix any $A\in \mathcal{F}$ and let $T=1_A$. Data processing — $H(T_{\#}\nu \Vert T_{\#}\mu )\le H(\nu \Vert \mu )$, itself an instance of Proposition 2's joint convexity applied to the conditional densities, equivalently the log-sum inequality — combined with the binary bound gives $2(\nu (A)-\mu (A){)}^2\le d(\nu (A)\Vert \mu (A))\le H(\nu \Vert \mu )$. Hence $|\nu (A)-\mu (A)|\le \sqrt{H(\nu \Vert \mu )/2}$ for every $A$, and taking the supremum over $A$ yields $\Vert \nu -\mu {\Vert }_{\mathrm{TV}}\le \sqrt{H(\nu \Vert \mu )/2}$. $\square$

Proposition 4 (Sanov upper bound for half-spaces). Let $L_n=\frac{1}{n}{\sum }_{i\le n}{\delta }_{X_i}$ for i.i.d. $X_i\sim \mu$. For a bounded continuous $g$ and a closed set $\Gamma \subseteq {\mathcal{M}}_1(\Omega )$ on which $\int gd\nu \ge c$ for all $\nu \in \Gamma$,

$$\underset{n}{\mathrm{limsup}}\frac{1}{n}\log \mathbb{P}(L_n\in \Gamma )\le -(c-{\Lambda }_{\mu }(g)).$$

Proof. On the event $\{L_n\in \Gamma \}$ one has $\int gd{L}_n\ge c$, so $1\{L_n\in \Gamma \}\le e^{n(\int gd{L}_n-c)}$. Taking expectations and using independence, $\mathbb{E}{e}^{n\int gd{L}_n}=\mathbb{E}{e}^{{\sum }_{i}g(X_i)}=(\int e^{g}d\mu {)}^n=e^{n{\Lambda }_{\mu }(g)}$. Hence $\mathbb{P}(L_n\in \Gamma )\le e^{-nc}{e}^{n{\Lambda }_{\mu }(g)}$; take $\frac{1}{n}\log$ and ${\mathrm{limsup}}_n$. Optimising over admissible $g$ via the Donsker-Varadhan formula replaces ${\sup }_g(c-{\Lambda }_{\mu }(g))$ by ${\inf }_{\nu \in \Gamma }H(\nu \Vert \mu )$, the Sanov upper bound. $\square$

Connections Master

• The convex-duality machinery is imported wholesale from the Legendre-Fenchel transform 37.07.03: relative entropy $H(\cdot \Vert \mu )$ is the Fenchel conjugate of the log-moment functional ${\Lambda }_{\mu }(g)=\log \int e^{g}d\mu$, the Donsker-Varadhan formula is the conjugacy pairing in infinite dimensions, and the optimal test function $g_{\star }=\log (d\nu /d\mu )$ is the analogue of the Fenchel-Young optimal tilt; Sanov's theorem stands to that unit's Cramér theorem as empirical measures stand to empirical means.

• The very definition $H(\nu \Vert \mu )=\int \log (d\nu /d\mu )d\nu$ rests on the Radon-Nikodym derivative of 02.07.08, and the chain rule $d\nu /d{\mu }_g=(d\nu /d\mu )e^{{\Lambda }_{\mu }(g)-g}$ used in the Donsker-Varadhan proof is exactly that unit's Radon-Nikodym chain rule; the relative entropy is finite precisely on the absolutely continuous pairs that unit characterises, and infinite otherwise.

• The truncation and convergence arguments that promote the Donsker-Varadhan supremum from bounded $g$ to the unbounded log-density $\log (d\nu /d\mu )$ use the monotone and dominated convergence apparatus of $L^p$ theory 02.07.06, and Pinsker's inequality is a statement comparing the $L^1$-type total-variation norm to the entropy on that same measure-theoretic footing.

• The thermodynamic free-energy/entropy duality 08.12.02 is the Gibbs-variational-principle reading of the same Donsker-Varadhan formula (Exercise 8): $-{\Lambda }_{\mu }(-g)$ is the free energy, $H(\cdot \Vert \mu )$ the entropy deficit, and the tilted Gibbs measure ${\mu }_g$ the equilibrium law; this unit isolates the probabilistic rate-function content rather than the equilibrium-statistical-mechanics content distinguished from the quantum relative entropy elsewhere in the corpus.

Historical & philosophical context Master

Relative entropy entered statistics through Solomon Kullback and Richard Leibler's 1951 paper On information and sufficiency ^{[Kullback & Leibler 1951]} (Annals of Mathematical Statistics 22, 79-86), which defined the divergence $\int \log (d\nu /d\mu )d\nu$ as a measure of the information for discriminating between two hypotheses and proved its additivity and non-negativity. The non-negativity itself is older, descending from J. Willard Gibbs's nineteenth-century inequality in statistical mechanics and from the convexity of $t\log t$ underlying Jensen's inequality. Ivan Sanov's 1957 paper ^{[Sanov 1957]} (Mat. Sbornik 42, 11-44) identified the divergence as the large-deviation rate function for empirical distributions of i.i.d. samples, the result now bearing his name.

The variational formula and the systematic use of relative entropy as a rate function in the large-deviations theory of Markov processes are due to Monroe Donsker and S. R. Srinivasa Varadhan in their 1975 series Asymptotic evaluation of certain Markov process expectations for large time ^{[Donsker & Varadhan 1975]} (Communications on Pure and Applied Mathematics 28, 1-47), work for which Varadhan received the 2007 Abel Prize. Imre Csiszár's 1967 information-geometric treatment ^{[Csiszár 1967]} established the joint convexity and the $f$-divergence framework, and gave the sharp Pinsker constant. Dembo and Zeitouni ^{[Dembo & Zeitouni §6.2]} and Dupuis and Ellis systematised the variational representation as the organising tool of modern large-deviation theory; the operational meaning as the optimal hypothesis-testing exponent is Stein's lemma, recorded by Cover and Thomas ^{[Cover & Thomas §11.6]}.

Bibliography Master

@article{kullback1951information,
  author  = {Kullback, Solomon and Leibler, Richard A.},
  title   = {On information and sufficiency},
  journal = {Annals of Mathematical Statistics},
  volume  = {22},
  number  = {1},
  pages   = {79--86},
  year    = {1951}
}

@article{donskervaradhan1975asymptotic,
  author  = {Donsker, Monroe D. and Varadhan, S. R. S.},
  title   = {Asymptotic evaluation of certain {Markov} process expectations for large time, {I}},
  journal = {Communications on Pure and Applied Mathematics},
  volume  = {28},
  number  = {1},
  pages   = {1--47},
  year    = {1975}
}

@article{sanov1957probability,
  author  = {Sanov, Ivan N.},
  title   = {On the probability of large deviations of random variables},
  journal = {Matematicheskii Sbornik},
  volume  = {42},
  pages   = {11--44},
  year    = {1957}
}

@article{csiszar1967information,
  author  = {Csisz\'ar, Imre},
  title   = {Information-type measures of difference of probability distributions and indirect observations},
  journal = {Studia Scientiarum Mathematicarum Hungarica},
  volume  = {2},
  pages   = {299--318},
  year    = {1967}
}

@book{dembozeitouni1998ldp,
  author    = {Dembo, Amir and Zeitouni, Ofer},
  title     = {Large Deviations Techniques and Applications},
  edition   = {2nd},
  series    = {Applications of Mathematics},
  number    = {38},
  publisher = {Springer},
  year      = {1998}
}

@book{coverthomas2006elements,
  author    = {Cover, Thomas M. and Thomas, Joy A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley-Interscience},
  year      = {2006}
}

@book{dupuisellis1997weak,
  author    = {Dupuis, Paul and Ellis, Richard S.},
  title     = {A Weak Convergence Approach to the Theory of Large Deviations},
  publisher = {Wiley},
  year      = {1997}
}

@book{deuschelstroock1989large,
  author    = {Deuschel, Jean-Dominique and Stroock, Daniel W.},
  title     = {Large Deviations},
  series    = {Pure and Applied Mathematics},
  number    = {137},
  publisher = {Academic Press},
  year      = {1989}
}