Cramér's Theorem and the Legendre-Fenchel Rate Function

Intuition Beginner

The law of large numbers promises that the average of many independent copies of a random quantity settles near its mean. Cramér's theorem answers the next question: when the average refuses to settle there — when it lands at some other value instead — how unlikely is that, exactly? The answer is an exponential decay, and Cramér's theorem hands you the precise number in the exponent.

That number comes from a single auxiliary function. Take your random quantity and look at the average of its exponential, tuned by a dial $\lambda$: large positive $\lambda$ rewards large outcomes, large negative $\lambda$ rewards small ones. The logarithm of this tuned average, as a function of the dial, is the cumulant generating function $\Lambda (\lambda )$. It is a smooth bowl-shaped curve that packages every moment of the variable at once. Cramér's insight is that the cost of seeing the average sit at a target value $x$ is obtained from $\Lambda$ by a geometric flip — the Legendre-Fenchel transform — that turns "dial language" into "outcome language."

Here is the picture for the two halves of the proof, which you have already met one piece of. To show a value is at most so likely, you bet on the dial: pick a $\lambda$, apply the exponential Markov inequality, and read off a bound. Optimising the dial gives the cheapest bound, and that cheapest bound is exactly the transformed cost. This is the upper half — the Chernoff bound.

To show the value is at least that likely, you cannot just wait for it; you have to make it happen. You re-weight the experiment so that the rare target becomes the new typical value — this re-weighting is called tilting — and under the re-weighted world the ordinary law of large numbers does the work. Then you carefully account for how much you paid to re-weight. The bill is, once again, the transformed cost. The two halves meet, and the exponential rate is pinned down.

So Cramér's theorem is two bets that agree: an upper bound bought by choosing the best dial, and a lower bound bought by tilting the experiment toward the rare event. Their meeting point is the rate function, and it is the conjugate of $\Lambda$.

Visual Beginner

Figure: two stacked panels sharing a horizontal outcome-axis. The top panel shows the cumulant generating function $\Lambda (\lambda )$ as a convex bowl over the dial-axis $\lambda$, with a tangent line of slope $x$ touching it; the height where that tangent meets the vertical axis (below zero) is minus the cost. The bottom panel shows the resulting rate function $I(x) = \Lambda^(x)$asaconvexvalleyovertheoutcome-axis$x$,dippingtoheightzeroexactlyatthemean$\mu$. An arrow labelled "Legendre-Fenchel flip" connects a slope in the top panel to a point in the bottom panel.*

   Lambda(lambda)            "dial" language
      |        _
      |       / \         tangent of slope x touches the bowl;
      |      /   \        its axis intercept is  -I(x)
      |  __ /     \__
------+----o---------o-----  lambda
      |   (intercept = -I(x))
                |
                |  Legendre-Fenchel flip  (slope x  ->  point x)
                v
   I(x)=Lambda*(x)          "outcome" language
      |\                 /
      | \               /     valley bottom at x = mu  (the mean),
      |  \             /      where I(mu)=0  (law of large numbers);
      |   \___     ___/       I(x) > 0 away from the mean = the
------+-------\_V_/---------- x   exponential cost of that deviation
                mu

Worked example Beginner

Roll a fair six-sided die many times and average the faces. The mean of one roll is $3.5$. We ask the cost of the average landing at $x=4$ instead, using a small piece of Cramér's recipe.

Step 1. Build the tuned average. For one die with faces $1$ through $6$, the tuned average is the ordinary average of the six tuned weights $e^{\lambda },e^{2\lambda },\dots ,e^{6\lambda }$, and $\Lambda (\lambda )$ is the logarithm of that average. We need the dial $\lambda$ that makes the re-weighted outcome equal to our target $4$.

Step 2. Match the target by the mean-under-tilt rule. Tilting by $\lambda$ re-weights face $k$ by $e^{\lambda k}$, so the re-weighted mean is the weighted face-total divided by the weight-total. Trying $\lambda =0.18$, the six weights $e^{0.18k}$ are $1.197,1.433,1.716,2.054,2.460,2.945$, with weight-total $11.805$; the weighted face-total is $1.197+2.866+5.148+8.216+12.30+17.67=47.40$, so the re-weighted mean is $47.40/11.805=4.015\approx 4$. Good enough for a hand computation.

Step 3. Read off the cost. The cost is $I(4)=\lambda \cdot 4-\Lambda (\lambda )$ at this $\lambda$. Here $\Lambda (0.18)=\log (11.805/6)=\log (1.9675)=0.6768$, so $$ I(4) = 0.18\times 4 - 0.6768 = 0.72 - 0.6768 = 0.0432. $$

Step 4. Read off the probability scale. Over $n=200$ rolls, the chance the average sits near $4$ decays like $e^{-nI(4)}=e^{-200\times 0.0432}=e^{-8.64}\approx 1.8\times 10^{-4}$.

What this tells us. A half-point shift in the die average, from $3.5$ to $4$, already costs about two parts in ten thousand at two hundred rolls — and it grows exponentially harsher with more rolls. The cost came from one dial setting and one subtraction, which is the whole computational content of Cramér's theorem at this level.

Check your understanding Beginner

Formal definition Intermediate+

Let $X_1,X_2,\dots$ be independent and identically distributed random vectors in ${\mathbb{R}}^d$ defined on a common probability space, with law $\mu$. Write $S_n=X_1+\cdots +X_n$ and let $$ \bar S_n := \frac{S_n}{n} = \frac{1}{n}\sum_{i=1}^n X_i $$ denote the empirical mean. By the strong law of large numbers 37.02.02, if $\mathbb{E}\Vert X_1\Vert <\infty$ then ${\bar{S}}_n\to {\mu }_{\ast }:=\mathbb{E}{X}_1$ almost surely; Cramér's theorem quantifies the exponentially small probability that ${\bar{S}}_n$ instead lies in a set away from ${\mu }_{\ast }$.

Definition (cumulant generating function). The logarithmic moment generating function (cumulant generating function) of $X_1$ is $$ \Lambda(\lambda) := \log \mathbb{E}, e^{\langle \lambda, X_1\rangle}, \qquad \lambda \in \mathbb{R}^d, $$ with values in $(-\infty ,+\infty ]$ and $⟨\lambda ,x⟩={\sum }_i{\lambda }_i{x}_i$. Its effective domain is ${\mathcal{D}}_{\Lambda }=\{\lambda :\Lambda (\lambda )<\infty \}$. The function $\Lambda$ is convex and lower-semicontinuous, $\Lambda (0)=0$, and $\nabla \Lambda (\lambda )={\mathbb{E}}_{\lambda }{X}_1$ is the mean of the tilted law ${\mathbb{P}}_{\lambda }$ wherever $\Lambda$ is differentiable 37.07.03.

Definition (Cramér rate function). The Cramér rate function is the Legendre-Fenchel conjugate of $\Lambda$, $$ \boxed{;I(x) ;=; \Lambda^(x) ;:=; \sup_{\lambda \in \mathbb{R}^d} \big( \langle \lambda, x\rangle - \Lambda(\lambda)\big), \qquad x \in \mathbb{R}^d.;} $$ By the conjugate machinery of 37.07.03, $\Lambda^$isconvex,lower-semicontinuous,andnon-negativewith$\Lambda^(\mu_) = 0$;when$0 \in \operatorname{int}\mathcal{D}_\Lambda$itismoreovera\ast \ast good\ast \ast ratefunction—itssublevelsets${x : \Lambda^*(x) \le \alpha}$ are compact. These are exactly the properties the LDP framework of 37.07.01 demands of a rate function.

Definition (exponential tilt / change of measure). For $\lambda \in {\mathcal{D}}_{\Lambda }$, the tilted law ${\mathbb{P}}_{\lambda }$ of $X_1$ is the probability measure with Radon-Nikodym derivative $$ \frac{d\mathbb{P}\lambda}{d\mu}(y) = e^{\langle\lambda, y\rangle - \Lambda(\lambda)}. $$ This is a probability measure because $\int e^{⟨\lambda ,y⟩-\Lambda (\lambda )}\mu (dy)=e^{-\Lambda (\lambda )}\mathbb{E}{e}^{⟨\lambda ,X_1⟩}=1$. Under $\mathbb{P}\lambda$the$X_i$remaini.i.d.withmean$\nabla\Lambda(\lambda)$andcumulantgeneratingfunction$\lambda' \mapsto \Lambda(\lambda + \lambda') - \Lambda(\lambda)$.

Theorem statement (Cramér). If $0\in \mathrm{int}{\mathcal{D}}_{\Lambda }$, the empirical means $\{{\bar{S}}_n\}$ satisfy the large deviation principle on ${\mathbb{R}}^d$ at speed $a_n=1/n$ with good rate function $I={\Lambda }^{\ast }$: for every closed $F$ and open $G$, $$ \limsup_{n} \tfrac{1}{n}\log\mathbb{P}(\bar S_n \in F) \le -\inf_{F}\Lambda^, \qquad \liminf_{n} \tfrac1n\log\mathbb{P}(\bar S_n \in G) \ge -\inf_{G}\Lambda^. $$

Counterexamples to common slips

• Heavy tails break the rate function, not just the constants. If $X_1$ is standard Cauchy then $\mathbb{E}{e}^{\lambda X_1}=\infty$ for every $\lambda \ne 0$, so ${\mathcal{D}}_{\Lambda }=\{0\}$, $\Lambda \equiv 0$ on its domain, and ${\Lambda }^{\ast }\equiv 0$. The empirical mean has no exponential concentration at all — the rate function is identically zero and Cramér's theorem says nothing because its hypothesis $0\in \mathrm{int}{\mathcal{D}}_{\Lambda }$ fails. Exponential decay of large deviations requires light (sub-exponential-tail) variables.
• The conjugate can be non-strictly-convex, and then the LDP rate is flat. For a variable supported on $\{0,1\}$ but degenerate ($\mathbb{P}(X=1)=1$), $\Lambda (\lambda )=\lambda$, so ${\Lambda }^{\ast }(1)=0$ and ${\Lambda }^{\ast }(x)=+\infty$ for $x\ne 1$. The rate function is an indicator, not a smooth valley; Cramér still holds, with the deterministic limit reflected as an infinite cost off the support.
• The infimum is over the right topological side. The upper bound is read on the closure of a set and the lower bound on its interior; using the same set for both can give a strictly smaller upper exponent than is correct, exactly the open/closed asymmetry isolated in 37.07.01.

Key theorem with proof Intermediate+

We prove Cramér's theorem in one dimension ($d=1$), the case that exhibits both mechanisms cleanly; the ${\mathbb{R}}^d$ extension is taken up at Master tier. Assume $0\in \mathrm{int}{\mathcal{D}}_{\Lambda }$, so all exponential moments are finite near the origin and $\Lambda$ is smooth and strictly convex on $\mathrm{int}{\mathcal{D}}_{\Lambda }$ (strict convexity unless $X_1$ is degenerate).

Theorem (Cramér in $\mathbb{R}$). Let $X_1,X_2,\dots$ be i.i.d. real random variables with $0\in \mathrm{int}{\mathcal{D}}_{\Lambda }$ and mean $\mu_ = \mathbb{E}X_1$.Then${\bar S_n}$satisfiestheLDPatspeed$1/n$withgoodratefunction$\Lambda^$.Inparticular,for$x > \mu_$,* $$ \lim_{n}\tfrac1n\log\mathbb{P}(\bar S_n \ge x) = -\Lambda^*(x). $$

Proof — upper bound (Chernoff). Fix a closed set $F$ and let $x\in F$ with $x\ge {\mu }_{\ast }$ (the case $x\le {\mu }_{\ast }$ is symmetric under $X\mapsto -X$). For any $\lambda \ge 0$, Markov's inequality applied to the non-negative variable $e^{\lambda S_n}$ gives, using independence, $$ \mathbb{P}(\bar S_n \ge x) = \mathbb{P}(S_n \ge nx) \le e^{-\lambda n x},\mathbb{E},e^{\lambda S_n} = e^{-\lambda n x}\big(\mathbb{E},e^{\lambda X_1}\big)^n = e^{-n(\lambda x - \Lambda(\lambda))}. $$ Taking $\frac{1}{n}\log$ and optimising over $\lambda \ge 0$, $$ \tfrac1n\log\mathbb{P}(\bar S_n \ge x) \le -\sup_{\lambda \ge 0}(\lambda x - \Lambda(\lambda)). $$ For $x\ge {\mu }_{\ast }={\Lambda }^{\prime }(0)$ the unconstrained supremum ${\Lambda }^{\ast }(x)={\sup }_{\lambda \in \mathbb{R}}(\lambda x-\Lambda (\lambda ))$ is attained at some ${\lambda }_x\ge 0$, because $\lambda \mapsto \lambda x-\Lambda (\lambda )$ has derivative $x-{\Lambda }^{\prime }(\lambda )$ which is non-negative at $\lambda =0$; hence the constraint $\lambda \ge 0$ is inactive and ${\sup }_{\lambda \ge 0}={\Lambda }^{\ast }(x)$. Therefore ${\mathrm{limsup}}_n\frac{1}{n}\log \mathbb{P}({\bar{S}}_n\ge x)\le -{\Lambda }^{\ast }(x)$. For a general closed $F$, ${\Lambda }^{\ast }$ is convex with minimum $0$ at ${\mu }_{\ast }$, so it is non-increasing to the left of ${\mu }_{\ast }$ and non-decreasing to the right; covering $F$ by the two rays $(-\infty ,x^{-}]$ and $[x^{+},\infty )$ where $x^{\pm }$ are the points of $F$ nearest ${\mu }_{\ast }$ on each side, and using the finite-union (max) rule of 37.07.01, yields ${\mathrm{limsup}}_n\frac{1}{n}\log \mathbb{P}({\bar{S}}_n\in F)\le -{\inf }_F{\Lambda }^{\ast }$.

Proof — lower bound (tilting). It suffices to prove that for every $x\in \mathrm{int}{\mathcal{D}}_{{\Lambda }^{\ast }}$ and every $\delta >0$, $$ \liminf_n \tfrac1n\log\mathbb{P}(|\bar S_n - x| < \delta) \ge -\Lambda^(x), $$ since every open $G$ contains such a ball around any of its points. Fix $x$ at which the supremum defining $\Lambda^(x)$isattainedataninterior$\lambda_x \in \operatorname{int}\mathcal{D}\Lambda$with$\Lambda'(\lambda_x) = x$(aso-called\ast \ast exposedpoint\ast \ast ;thisholdsthroughout$\operatorname{int}\mathcal{D}{\Lambda^}$underthestandinghypothesis).Introducethetiltedlaw$\mathbb{P}{\lambda_x}$with$d\mathbb{P}{\lambda_x}/d\mu = e^{\lambda_x y - \Lambda(\lambda_x)}$;underitthe$X_i$arei.i.d.withmean$\Lambda'(\lambda_x) = x$andfinitevariance$\Lambda''(\lambda_x)$.Reversingthechangeofmeasureontheevent$A_n = {|\bar S_n - x| < \delta}$, $$ \mathbb{P}(A_n) = \mathbb{E}{\lambda_x}\Big[\mathbf{1}{A_n},e^{-\lambda_x S_n + n\Lambda(\lambda_x)}\Big]. $$ On $A_n$ one has $S_n=n{\bar{S}}_n\in (n(x-\delta ),n(x+\delta ))$, so $e^{-{\lambda }_x{S}_n}\ge e^{-n{\lambda }_{x}x-n|{\lambda }_x|\delta }$ (taking the worse sign), giving $$ \mathbb{P}(A_n) \ge e^{-n(\lambda_x x - \Lambda(\lambda_x)) - n|\lambda_x|\delta},\mathbb{P}_{\lambda_x}(A_n) = e^{-n\Lambda^(x) - n|\lambda_x|\delta},\mathbb{P}_{\lambda_x}(A_n), $$ where the Fenchel-Young equality ${\Lambda }^{\ast }(x)={\lambda }_{x}x-\Lambda ({\lambda }_x)$ at the exposed tilt was used 37.07.03.

Under ${\mathbb{P}}_{{\lambda }_x}$ the mean of ${\bar{S}}_n$ is exactly $x$, so the weak law of large numbers gives ${\mathbb{P}}_{{\lambda }_x}(A_n)\to 1$, hence $\frac{1}{n}\log {\mathbb{P}}_{{\lambda }_x}(A_n)\to 0$. Therefore $$ \liminf_n \tfrac1n\log\mathbb{P}(A_n) \ge -\Lambda^(x) - |\lambda_x|\delta, $$ and letting $\delta \downarrow 0$ yields the claim. The full lower bound on open $G$ follows by taking the supremum over $x\in G$. Combined with goodness of $\Lambda^$from[\mathrm{37.07.03}],thetwoboundsconstitutetheLDP.$\square$

Bridge. This theorem builds toward the entire applied large-deviations toolkit — hypothesis testing, queueing overflow, statistical-mechanics entropy — and appears again in the Gärtner-Ellis theorem 37.07.04, where the identical Chernoff-and-tilting pair is run against a limiting cumulant generating function instead of a single-sample one. This is exactly the realisation of the abstract weak-LDP-plus-tightness scheme of 37.07.01: the tilting lower bound and Chernoff upper bound are the local content that produces the weak LDP, and finiteness of $\Lambda$ near $0$ supplies the exponential tightness that upgrades it. The central insight is that the upper bound optimises a free dial $\lambda$ while the lower bound realises the optimal dial as a change of measure, so the supremum defining ${\Lambda }^{\ast }$ is computed twice — once as a bound, once as a construction — and the answers coincide by Fenchel-Young equality. Putting these together, Cramér's theorem generalises the law of large numbers 37.02.02 from a statement about where the mean goes to a statement about the price of going elsewhere, and is dual to the moment-generating description through the Legendre-Fenchel transform of 37.07.03.

Exercises Intermediate+

Advanced results Master

Cramér in ${\mathbb{R}}^d$: the convex upper bound and exposed-point lower bound

In $d$ dimensions the upper bound is assembled from supporting half-spaces and the lower bound from exposed points. For the upper bound, a compact set is covered by finitely many half-spaces $H_i=\{x:⟨{\lambda }_i,x⟩\ge ⟨{\lambda }_i,x{⟩}_i\}$, on each of which the scalar Chernoff estimate applies to $⟨{\lambda }_i,X⟩$; the finite-union rule of 37.07.01 combines them, and exponential tightness — supplied by finiteness of $\Lambda$ on a ball around $0$ via the coercive functional $U(x)=\Vert x\Vert$ — extends the bound from compacts to all closed sets ^{[Dembo & Zeitouni §2.2]}. For the lower bound, one shows ${\mathrm{liminf}}_n\frac{1}{n}\log \mathbb{P}({\bar{S}}_n\in G)\ge -{\Lambda }^{\ast }(x)$ for every exposed point $x$ of ${\Lambda }^{\ast }$ with exposing hyperplane in $\mathrm{int}{\mathcal{D}}_{\Lambda }$, by tilting along the exposing direction exactly as in $d=1$; the convex-duality theorem that exposed points are dense in $\mathrm{dom}{\Lambda }^{\ast }$ (under $0\in \mathrm{int}{\mathcal{D}}_{\Lambda }$) upgrades the pointwise bound to all open sets. The result is the LDP with good rate ${\Lambda }^{\ast }$ on ${\mathbb{R}}^d$.

The role of exposed points and the gap when steepness fails

An $x$ is exposed for ${\Lambda }^{\ast }$ if there is $\lambda$ with ${\Lambda }^{\ast }(y)>{\Lambda }^{\ast }(x)+⟨\lambda ,y-x⟩$ for all $y\ne x$, i.e. a hyperplane touching ${\Lambda }^{\ast }$ only at $x$. The lower bound needs the exposing $\lambda$ to lie in $\mathrm{int}{\mathcal{D}}_{\Lambda }$ so the tilt ${\mathbb{P}}_{\lambda }$ is defined and has mean $x$. When $\Lambda$ is steep ($|\nabla \Lambda (\lambda )|\to \infty$ as $\lambda \to \partial {\mathcal{D}}_{\Lambda }$), every $x\in \mathrm{int}{\mathcal{D}}_{{\Lambda }^{\ast }}$ is exposed with exposing tilt interior, and the lower bound holds throughout. Without steepness, points $x$ corresponding to boundary tilts may fail to be exposed, and the rate function can drop below ${\Lambda }^{\ast }$ at such $x$ — the same loss of surjectivity of $\nabla \Lambda$ seen for $\sqrt{1+{\lambda }^2}$ in 37.07.03, now controlling whether the LDP rate is the full conjugate or only its exposed restriction.

Bahadur-Rao exact asymptotics

Cramér's theorem gives the exponential rate; the prefactor is the Bahadur-Rao refinement ^{[Bahadur & Rao 1960]}. For a non-lattice real variable and $x>{\mu }_{\ast }$ with optimal tilt ${\lambda }_x$, $$ \mathbb{P}(\bar S_n \ge x) = \frac{e^{-n\Lambda^(x)}}{\lambda_x\sqrt{2\pi n,\Lambda''(\lambda_x)}},\big(1 + o(1)\big). $$ The exponential factor is Cramér; the algebraic prefactor $1/({\lambda }_x\sqrt{2\pi n{\Lambda }^{\prime \prime }({\lambda }_x)})$ comes from a local central limit theorem under the tilted law, where ${\bar{S}}_n$ is asymptotically Gaussian with variance ${\Lambda }^{\prime \prime }({\lambda }_x)/n$ centred at $x$. This exhibits the tilting argument as not merely a bound but the exact saddle-point evaluation: the tilt that achieves $\Lambda^(x)$isthesaddleoftheinverse-Laplaceintegralforthedensityof$\bar S_n$.

Sub-additivity and the abstract Cramér theorem

The i.i.d. structure can be relaxed to a sub-additivity condition. If $c_n(x):=-\log \mathbb{P}({\bar{S}}_n\in B(x,\delta ))$ satisfies an approximate super-additivity $c_{m+n}\le c_m+c_n+o(m+n)$, the limit ${\lim }_n\frac{1}{n}{c}_n(x)$ exists by Fekete's lemma and defines the rate function intrinsically, with no recourse to $\Lambda$. This abstract Cramér theorem (Bahadur-Zabell) recovers ${\Lambda }^{\ast }$ when the increments are i.i.d. but extends to additive functionals of Markov chains and stationary sequences, where $\Lambda$ is replaced by the limiting log-spectral-radius of a tilted transition kernel — the bridge to Gärtner-Ellis 37.07.04.

Synthesis. The central insight of Cramér's theorem is that one convex function $\Lambda$ and its conjugate ${\Lambda }^{\ast }$ encode the entire large-deviation behaviour of i.i.d. averages, so the principle is exactly the LDP realisation of the conjugacy proved abstractly in 37.07.03, with the goodness of ${\Lambda }^{\ast }$ inherited from finiteness of $\Lambda$ near the origin. The foundational reason the upper and lower bounds coincide is that both compute the same supremum ${\Lambda }^{\ast }(x)={\sup }_{\lambda }(⟨\lambda ,x⟩-\Lambda (\lambda ))$ — the Chernoff bound optimises the dial, the tilting construction realises the optimal dial as a change of measure, and Fenchel-Young equality identifies the two. Putting these together with the strong law 37.02.02 shows Cramér generalises the law of large numbers from concentration at ${\mu }_{\ast }$ to the exact exponential price of any deviation, while the bridge is exponential tightness: finiteness of $\Lambda$ on a neighbourhood of $0$ both makes ${\Lambda }^{\ast }$ good and supplies the tightness that upgrades the weak LDP of 37.07.01 to the full principle. The construction appears again in Sanov's theorem 37.07.06 as the level-1 contraction of the level-2 empirical-measure LDP, and is dual to the Gärtner-Ellis route 37.07.04 which keeps the conjugacy machinery while discarding independence.

Full proof set Master

Proposition 1 (Chernoff upper bound, scalar form). Let $X_1,X_2,\dots$ be i.i.d. real with $\Lambda (\lambda )=\log \mathbb{E}{e}^{\lambda X_1}$. For every $x\in \mathbb{R}$, $\limsup_n\tfrac1n\log\mathbb{P}(\bar S_n \ge x) \le -\Lambda^(x)$when$x \ge \mu_*$,andsymmetricallyfor$x \le \mu_*$.*

Proof. For $\lambda \ge 0$, Markov's inequality on $e^{\lambda S_n}\ge 0$ gives $\mathbb{P}(S_n\ge nx)\le e^{-\lambda nx}\mathbb{E}{e}^{\lambda S_n}=e^{-n(\lambda x-\Lambda (\lambda ))}$ by independence. Hence $\frac{1}{n}\log \mathbb{P}({\bar{S}}_n\ge x)\le -(\lambda x-\Lambda (\lambda ))$ for every $\lambda \ge 0$, so taking the infimum over the bound, $\le -{\sup }_{\lambda \ge 0}(\lambda x-\Lambda (\lambda ))$. For $x\ge {\mu }_{\ast }={\Lambda }^{\prime }(0)$, the concave map $\lambda \mapsto \lambda x-\Lambda (\lambda )$ has non-negative derivative $x-{\Lambda }^{\prime }(0)$ at $0$, so its maximiser lies in $[0,\infty )$ and ${\sup }_{\lambda \ge 0}={\sup }_{\lambda \in \mathbb{R}}={\Lambda }^{\ast }(x)$. The $\mathrm{limsup}$ over $n$ of a constant-in-$n$ bound is the bound itself. $\square$

Proposition 2 (tilting lower bound at an exposed point). Let $x$ be exposed for $\Lambda^$withexposingtilt$\lambda_x \in \operatorname{int}\mathcal{D}_\Lambda$satisfying$\Lambda'(\lambda_x) = x$.Thenforeveryopen$G \ni x$,$\liminf_n \tfrac1n\log\mathbb{P}(\bar S_n \in G) \ge -\Lambda^(x)$.

Proof. Choose $\delta >0$ with $B(x,\delta )\subseteq G$. Tilt by ${\lambda }_x$: under ${\mathbb{P}}_{{\lambda }_x}$ with $d{\mathbb{P}}_{{\lambda }_x}/d\mu =e^{{\lambda }_{x}y-\Lambda ({\lambda }_x)}$, the $X_i$ are i.i.d. with mean ${\Lambda }^{\prime }({\lambda }_x)=x$ and finite variance ${\Lambda }^{\prime \prime }({\lambda }_x)$ (Exercise 4). Changing measure back, $$ \mathbb{P}(\bar S_n \in B(x,\delta)) = \mathbb{E}{\lambda_x}\big[\mathbf{1}{{\bar S_n \in B(x,\delta)}},e^{-\lambda_x S_n + n\Lambda(\lambda_x)}\big] \ge e^{-n\lambda_x x - n|\lambda_x|\delta + n\Lambda(\lambda_x)},\mathbb{P}{\lambda_x}(\bar S_n \in B(x,\delta)), $$ where on the event $|{\bar{S}}_n-x|<\delta$ one bounds $-{\lambda }_x{S}_n\ge -n{\lambda }_{x}x-n|{\lambda }_x|\delta$. The exponent is $-n({\lambda }_{x}x-\Lambda ({\lambda }_x))-n|{\lambda }_x|\delta =-n{\Lambda }^{\ast }(x)-n|{\lambda }_x|\delta$ by Fenchel-Young equality at the exposed point. Since $\mathbb{E}{\lambda_x}\bar S_n = x$,theweaklawgives$\mathbb{P}_{\lambda_x}(\bar S_n \in B(x,\delta)) \to 1$,soits$\tfrac1n\log \to 0$.Thus$\liminf_n\tfrac1n\log\mathbb{P}(\bar S_n\in G) \ge -\Lambda^*(x) - |\lambda_x|\delta$,and$\delta\downarrow0$closesit.$\square$

Proposition 3 (the tilted measure is a probability measure with shifted cumulants). For $\lambda \in {\mathcal{D}}_{\Lambda }$, the tilt ${\mathbb{P}}_{\lambda }$ defined by $d{\mathbb{P}}_{\lambda }/d\mu =e^{⟨\lambda ,y⟩-\Lambda (\lambda )}$ is a probability measure, and its cumulant generating function is ${\Lambda }_{\lambda }(\theta )=\Lambda (\lambda +\theta )-\Lambda (\lambda )$.

Proof. Total mass: $\int e^{⟨\lambda ,y⟩-\Lambda (\lambda )}\mu (dy)=e^{-\Lambda (\lambda )}\int e^{⟨\lambda ,y⟩}\mu (dy)=e^{-\Lambda (\lambda )}\cdot e^{\Lambda (\lambda )}=1$, and the density is non-negative, so ${\mathbb{P}}_{\lambda }$ is a probability measure equivalent to $\mu$ on ${\mathcal{D}}_{\Lambda }$. Its moment generating function at $\theta$ is $$ \int e^{\langle\theta,y\rangle},d\mathbb{P}\lambda = \int e^{\langle\theta,y\rangle}e^{\langle\lambda,y\rangle - \Lambda(\lambda)}\mu(dy) = e^{-\Lambda(\lambda)}\int e^{\langle\lambda+\theta,y\rangle}\mu(dy) = e^{\Lambda(\lambda+\theta) - \Lambda(\lambda)}, $$ so $\Lambda\lambda(\theta) = \log$ofthisis$\Lambda(\lambda+\theta) - \Lambda(\lambda)$.Differentiatingat$\theta = 0$recovers$\nabla\Lambda(\lambda)$asthetiltedmean,thefactpoweringProposition2.$\square$

Connections Master

• The rate function ${\Lambda }^{\ast }$ of this unit is precisely the abstract good rate function whose axioms are laid out in 37.07.01; that unit's weak-LDP-plus-exponential-tightness upgrade is the scaffold on which the present Chernoff-and-tilting proof hangs, and the exponential tightness it requires is supplied here by finiteness of $\Lambda$ on a neighbourhood of the origin.

• The conjugacy $I={\Lambda }^{\ast }$ and the convexity, goodness, and Fenchel-Young equality used throughout are imported wholesale from 37.07.03; the optimal exponential tilt ${\lambda }_x$ realising the cost is the subgradient ${\lambda }_x\in \partial {\Lambda }^{\ast }(x)$, the equality case of the Fenchel-Young inequality proved there.

• The law of large numbers 37.02.02 is the degenerate $\inf I=0$ statement underneath Cramér: ${\Lambda }^{\ast }$ vanishes only at ${\mu }_{\ast }$, so the empirical mean concentrates there at the exponential rate ${\Lambda }^{\ast }$, sharpening "the average converges to the mean" into "the average leaves the mean only with exponentially small probability."

• The ${\mathbb{R}}^d$ upper bound's reduction to supporting half-spaces is an application of the Hahn-Banach separation theorem 02.11.02; the same geometric separation that powers biconjugation in 37.07.03 here separates a convex deviation set from the mean to produce the dominating half-space on which the scalar Chernoff bound acts.

Historical & philosophical context Master

Harald Cramér proved the one-dimensional theorem in 1938 ^{[Cramér 1938]} for sums of i.i.d. variables possessing an analytic moment generating function, identifying the exponential rate as the conjugate of the cumulant generating function; he worked within the analytic-density framework of the Edgeworth and saddle-point tradition rather than the modern measure-theoretic LDP. The change-of-measure (tilting) technique that gives the lower bound was implicit in Cramér's saddle-point analysis and was made into a clean probabilistic argument by Esscher, whose name attaches to the "Esscher transform" in actuarial mathematics — the same exponential re-weighting. The exponential Markov inequality underlying the upper bound was systematised by Herman Chernoff in 1952 ^{[Chernoff 1952]} in the context of asymptotically efficient hypothesis tests, and now carries his name.

The removal of the analyticity hypothesis and the recasting in the abstract LDP language is due to the development by Bahadur, Zabell, Lanford, Ellis, and others through the 1960s and 1970s; the exposed-point analysis controlling the ${\mathbb{R}}^d$ lower bound and the steepness condition were clarified by Gärtner and by Ellis ^{[Ellis 1985]}. Bahadur and Rao computed the exact prefactor in 1960 ^{[Bahadur & Rao 1960]}, showing Cramér's exponential rate to be the leading term of a full saddle-point expansion. The systematic textbook treatment, including the convex-duality and exposed-point machinery used here, is that of Dembo and Zeitouni ^{[Dembo & Zeitouni §2.2]}.

Bibliography Master

@article{cramer1938nouveau,
  author  = {Cram\'er, Harald},
  title   = {Sur un nouveau th\'eor\`eme-limite de la th\'eorie des probabilit\'es},
  journal = {Actualit\'es Scientifiques et Industrielles},
  volume  = {736},
  pages   = {5--23},
  year    = {1938}
}

@article{chernoff1952measure,
  author  = {Chernoff, Herman},
  title   = {A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations},
  journal = {Annals of Mathematical Statistics},
  volume  = {23},
  number  = {4},
  pages   = {493--507},
  year    = {1952}
}

@article{bahadurrao1960deviations,
  author  = {Bahadur, R. R. and Rao, R. Ranga},
  title   = {On deviations of the sample mean},
  journal = {Annals of Mathematical Statistics},
  volume  = {31},
  number  = {4},
  pages   = {1015--1027},
  year    = {1960}
}

@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{ellis1985entropy,
  author    = {Ellis, Richard S.},
  title     = {Entropy, Large Deviations, and Statistical Mechanics},
  series    = {Grundlehren der mathematischen Wissenschaften},
  number    = {271},
  publisher = {Springer},
  year      = {1985}
}

@book{denhollander2000large,
  author    = {den Hollander, Frank},
  title     = {Large Deviations},
  series    = {Fields Institute Monographs},
  number    = {14},
  publisher = {American Mathematical Society},
  year      = {2000}
}