Cramér's Theorem

Beyond the CLT: The Regime of Rare Events

The central limit theorem tells us that the sample mean Xˉn\bar{X}_n fluctuates around μ\mu at scale 1/n1/\sqrt{n}, and the fluctuations are approximately Gaussian. But what about large deviations — the probability that Xˉn\bar{X}_n deviates from μ\mu by a fixed amount δ>0\delta > 0, regardless of nn? The CLT says this probability goes to zero, but it does not tell us how fast. Large deviations theory provides the answer: the decay is exponential in nn, and the rate is governed by a function I(x)I(x) that encodes the cost of forcing the sample mean to take the value xx. This is the rate function, and Cramér's theorem identifies it as the Legendre-Fenchel transform of the log-MGF.

Definition:

Cumulant Generating Function

Let XX be a real-valued random variable with moment generating function MX(θ)=E[eθX]M_X(\theta) = \mathbb{E}[e^{\theta X}]. The cumulant generating function (CGF) is defined as Λ(θ)≜log⁡MX(θ)=log⁡E[eθX].\Lambda(\theta) \triangleq \log M_X(\theta) = \log \mathbb{E}[e^{\theta X}]. The effective domain of Λ\Lambda is DΛ={θ∈R:Λ(θ)<∞}\mathcal{D}_\Lambda = \{\theta \in \mathbb{R} : \Lambda(\theta) < \infty\}.

The CGF is always convex (it is the log of a positive linear functional evaluated at an exponential family). Its derivatives at θ=0\theta = 0 give the cumulants: Λ′(0)=μ\Lambda'(0) = \mu, Λ′′(0)=σ2\Lambda''(0) = \sigma^2.

Example: CGF of a N(μ,σ2)\mathcal{N}(\mu, \sigma^2) Random Variable

Compute the cumulant generating function Λ(θ)\Lambda(\theta) for X∼N(μ,σ2)X \sim \mathcal{N}(\mu, \sigma^2).

Solution
Compute the MGF

For X∼N(μ,σ2)X \sim \mathcal{N}(\mu, \sigma^2): MX(θ)=E[eθX]=exp⁡ ⁣(μθ+σ2θ22).M_X(\theta) = \mathbb{E}[e^{\theta X}] = \exp\!\left(\mu\theta + \frac{\sigma^2 \theta^2}{2}\right).

Take the logarithm

Λ(θ)=log⁡MX(θ)=μθ+σ2θ22.\Lambda(\theta) = \log M_X(\theta) = \mu\theta + \frac{\sigma^2 \theta^2}{2}.ThisisaquadraticinThis is a quadratic in\theta,definedforall, defined for all\theta \in \mathbb{R}.Thefirstcumulantis. The first cumulant is\Lambda'(0) = \muandthesecondisand the second is\Lambda''(0) = \sigma^2$.

Definition:

Rate Function (Fenchel-Legendre Transform)

The rate function associated with a random variable XX is the Fenchel-Legendre transform of the CGF: I(x)≜Λ∗(x)=sup⁡θ∈R{θx−Λ(θ)}.I(x) \triangleq \Lambda^*(x) = \sup_{\theta \in \mathbb{R}} \bigl\{\theta x - \Lambda(\theta)\bigr\}. Since Λ\Lambda is convex, II is also convex. It satisfies I(x)≥0I(x) \geq 0 for all xx and I(μ)=0I(\mu) = 0 where μ=E[X]\mu = \mathbb{E}[X].

The rate function I(x)I(x) quantifies the "cost" of observing the sample mean at xx. The minimum cost is zero, attained at the true mean — the most likely value. The further xx deviates from μ\mu, the larger I(x)I(x), and the faster the probability decays.

Example: Rate Function for N(μ,σ2)\mathcal{N}(\mu, \sigma^2)

Compute the rate function I(x)I(x) for X∼N(μ,σ2)X \sim \mathcal{N}(\mu, \sigma^2) using the Legendre transform of Λ(θ)=μθ+σ2θ2/2\Lambda(\theta) = \mu\theta + \sigma^2\theta^2/2.

Solution
Set up the optimization

I(x)=sup⁡θ{θx−μθ−σ2θ22}.I(x) = \sup_{\theta} \left\{\theta x - \mu\theta - \frac{\sigma^2\theta^2}{2}\right\}.$

Take derivative and set to zero

ddθ[θx−μθ−σ2θ22]=x−μ−σ2θ=0  ⟹  θ∗=x−μσ2.\frac{d}{d\theta}\left[\theta x - \mu\theta - \frac{\sigma^2\theta^2}{2}\right] = x - \mu - \sigma^2\theta = 0 \implies \theta^* = \frac{x - \mu}{\sigma^2}.$

Substitute back

I(x)=(x−μ)σ2⋅x−μ⋅(x−μ)σ2−σ22⋅(x−μ)2σ4=(x−μ)22σ2.I(x) = \frac{(x-\mu)}{\sigma^2} \cdot x - \mu \cdot \frac{(x-\mu)}{\sigma^2} - \frac{\sigma^2}{2}\cdot\frac{(x-\mu)^2}{\sigma^4} = \frac{(x - \mu)^2}{2\sigma^2}.TheratefunctionisaparabolacenteredatThe rate function is a parabola centered at\mu.ThisisconsistentwiththeGaussiantail:. This is consistent with the Gaussian tail:\mathbb{P}(\bar{X}_n \geq a) \approx \exp!\left(-n \cdot \frac{(a-\mu)^2}{2\sigma^2}\right)$.

Example: Rate Function for Bernoulli(pp)

Compute I(x)I(x) for X∼Bernoulli(p)X \sim \text{Bernoulli}(p).

Solution
CGF

MX(θ)=(1−p)+peθM_X(\theta) = (1-p) + pe^{\theta}, so Λ(θ)=log⁡((1−p)+peθ)\Lambda(\theta) = \log\bigl((1-p) + pe^{\theta}\bigr).

Legendre transform

Setting d/dθ[θx−Λ(θ)]=0d/d\theta[\theta x - \Lambda(\theta)] = 0: x=peθ∗(1−p)+peθ∗.x = \frac{pe^{\theta^*}}{(1-p) + pe^{\theta^*}}. Solving for eθ∗=x(1−p)p(1−x)e^{\theta^*} = \frac{x(1-p)}{p(1-x)} and substituting: I(x)=xlog⁡xp+(1−x)log⁡1−x1−pI(x) = x \log\frac{x}{p} + (1-x)\log\frac{1-x}{1-p} for x∈[0,1]x \in [0, 1]. This is exactly the KL divergence D(Ber(x)∥Ber(p))D(\text{Ber}(x) \| \text{Ber}(p)).

Interpretation

The rate function for Bernoulli i.i.d. sums is the binary KL divergence. The probability that the empirical frequency of ones equals xx decays as exp⁡(−n⋅D(Ber(x)∥Ber(p)))\exp(-n \cdot D(\text{Ber}(x) \| \text{Ber}(p))). This foreshadows Sanov's theorem in the next section.

,

Rate Function

A non-negative, lower semicontinuous, convex function I(x)I(x) such that P(Xˉn∈A)≈exp⁡(−ninf⁡x∈AI(x))\mathbb{P}(\bar{X}_n \in A) \approx \exp(-n \inf_{x \in A} I(x)) for large nn. Obtained as the Legendre-Fenchel transform of the cumulant generating function.

Related: Cumulant Generating Function, Large Deviation Principle

Theorem: Cramér's Theorem

Let X1,X2,…X_1, X_2, \ldots be i.i.d. real-valued random variables with cumulant generating function Λ(θ)=log⁡E[eθX1]\Lambda(\theta) = \log \mathbb{E}[e^{\theta X_1}] finite in a neighborhood of the origin. Let Xˉn=1n∑i=1nXi\bar{X}_n = \frac{1}{n}\sum_{i=1}^n X_i and define I(x)=sup⁡θ{θx−Λ(θ)}I(x) = \sup_\theta \{\theta x - \Lambda(\theta)\}. Then for any closed set FF: lim sup⁡n→∞1nlog⁡P(Xˉn∈F)≤−inf⁡x∈FI(x),\limsup_{n \to \infty} \frac{1}{n} \log \mathbb{P}(\bar{X}_n \in F) \leq -\inf_{x \in F} I(x), and for any open set GG: lim inf⁡n→∞1nlog⁡P(Xˉn∈G)≥−inf⁡x∈GI(x).\liminf_{n \to \infty} \frac{1}{n} \log \mathbb{P}(\bar{X}_n \in G) \geq -\inf_{x \in G} I(x). In particular, for a>μ=E[X1]a > \mu = \mathbb{E}[X_1]: P(Xˉn≥a)≐e−nI(a),\mathbb{P}(\bar{X}_n \geq a) \doteq e^{-nI(a)}, where ≐\doteq denotes logarithmic equivalence (equal exponential rates).

Rare events happen, and when they do, they happen in the "most likely unlikely way." To force Xˉn=a>μ\bar{X}_n = a > \mu, the i.i.d. samples conspire in the cheapest possible way, and the cost of this conspiracy is exactly I(a)I(a) nats per sample. The probability of the event decays exponentially at rate I(a)I(a) per sample.

Show Hint

Start with the Chernoff bound: P(Xˉn≥a)≤e−nsup⁡θ{θa−Λ(θ)}=e−nI(a)\mathbb{P}(\bar{X}_n \geq a) \leq e^{-n\sup_\theta\{\theta a - \Lambda(\theta)\}} = e^{-nI(a)}.

For the matching lower bound, use the exponential change of measure (tilting) technique.

Under the tilted measure dQθ=eθX−Λ(θ)dPd\mathbb{Q}_\theta = e^{\theta X - \Lambda(\theta)} dP, the mean shifts to Λ′(θ∗)\Lambda'(\theta^*).

Proof
Upper bound (Chernoff)

For any θ>0\theta > 0: P(Xˉn≥a)=P ⁣(eθ∑iXi≥enθa)≤E[eθ∑iXi]enθa=en[Λ(θ)−θa].\mathbb{P}(\bar{X}_n \geq a) = \mathbb{P}\!\left(e^{\theta \sum_i X_i} \geq e^{n\theta a}\right) \leq \frac{\mathbb{E}[e^{\theta \sum_i X_i}]}{e^{n\theta a}} = e^{n[\Lambda(\theta) - \theta a]}. Optimizing over θ\theta: P(Xˉn≥a)≤e−nsup⁡θ{θa−Λ(θ)}=e−nI(a)\mathbb{P}(\bar{X}_n \geq a) \leq e^{-n\sup_\theta\{\theta a - \Lambda(\theta)\}} = e^{-nI(a)}.

Lower bound via tilting

Choose θ∗\theta^* such that Λ′(θ∗)=a\Lambda'(\theta^*) = a (the tilting parameter). Define the tilted distribution dPθ∗(x)=eθ∗x−Λ(θ∗)dP(x)dP_{\theta^*}(x) = e^{\theta^* x - \Lambda(\theta^*)} dP(x). Under Pθ∗P_{\theta^*}, each XiX_i has mean aa and finite variance σθ∗2=Λ′′(θ∗)\sigma_{\theta^*}^2 = \Lambda''(\theta^*).

Apply CLT under tilted measure

Under Pθ∗P_{\theta^*}, Xˉn\bar{X}_n concentrates around aa. For δ>0\delta > 0: Pθ∗(a−δ≤Xˉn≤a+δ)→1.P_{\theta^*}(a - \delta \leq \bar{X}_n \leq a + \delta) \to 1. On the event {Xˉn∈[a−δ,a+δ]}\{\bar{X}_n \in [a-\delta, a+\delta]\}, the likelihood ratio satisfies dP/dPθ∗=e−θ∗nXˉn+nΛ(θ∗)≥e−n[θ∗(a+δ)−Λ(θ∗)]dP/dP_{\theta^*} = e^{-\theta^* n\bar{X}_n + n\Lambda(\theta^*)} \geq e^{-n[\theta^*(a+\delta) - \Lambda(\theta^*)]}.

Combine

P(Xˉn≥a)≥P(a−δ≤Xˉn≤a+δ)≥e−n[θ∗(a+δ)−Λ(θ∗)]⋅Pθ∗(Xˉn∈[a−δ,a+δ]).KATEXPLACEHOLDER0ENDlim inf⁡n→∞1nlog⁡P(Xˉn≥a)≥−[θ∗a−Λ(θ∗)]=−I(a).■\mathbb{P}(\bar{X}_n \geq a) \geq \mathbb{P}(a - \delta \leq \bar{X}_n \leq a + \delta) \geq e^{-n[\theta^*(a+\delta) - \Lambda(\theta^*)]} \cdot P_{\theta^*}(\bar{X}_n \in [a-\delta, a+\delta]).KATEXPLACEHOLDER0END\liminf_{n \to \infty} \frac{1}{n}\log \mathbb{P}(\bar{X}_n \geq a) \geq -[\theta^* a - \Lambda(\theta^*)] = -I(a). \quad \blacksquare$

,

Historical Note: Harald Cramér and the Birth of Large Deviations

1938--2007

Harald Cramér (1893--1985), a Swedish mathematician and statistician, published his foundational result on the exponential decay of tail probabilities in 1938. Working on problems in insurance mathematics — specifically, the ruin probability of an insurance company — Cramér needed precise asymptotics for sums of i.i.d. random variables far from the mean. His 1938 paper established the exponential decay rate and the role of the Legendre transform, though the full measure-theoretic framework was developed later by Varadhan, who received the Abel Prize in 2007 partly for his work on large deviations.

Logarithmic Equivalence

Two sequences ana_n and bnb_n are logarithmically equivalent, written an≐bna_n \doteq b_n, if lim⁡n→∞1nlog⁡(an/bn)=0\lim_{n \to \infty} \frac{1}{n}\log(a_n/b_n) = 0. In large deviations, P(Xˉn≥a)≐e−nI(a)\mathbb{P}(\bar{X}_n \geq a) \doteq e^{-nI(a)} means the probability decays at exactly the exponential rate I(a)I(a), up to sub-exponential factors.

Related: Rate Function (Fenchel-Legendre Transform)

Exponential Tilting as Importance Sampling

The tilted distribution dPθ=eθx−Λ(θ)dPdP_\theta = e^{\theta x - \Lambda(\theta)}dP shifts the mean of XX from μ\mu to Λ′(θ)\Lambda'(\theta). This is exactly the importance sampling change of measure used in Monte Carlo simulation of rare events. To estimate P(Xˉn≥a)\mathbb{P}(\bar{X}_n \geq a) efficiently, one simulates under Pθ∗P_{\theta^*} (where θ∗\theta^* makes aa the new mean) and corrects with the likelihood ratio. This is not just a proof technique — it is the foundation of the most effective rare-event simulation methods.

Rate Function I(x)I(x) for Common Distributions

Visualize the rate function I(x)=sup⁡θ{θx−Λ(θ)}I(x) = \sup_\theta\{\theta x - \Lambda(\theta)\} for Gaussian, Bernoulli, and Poisson distributions. Observe how the parabolic shape of the Gaussian rate function contrasts with the KL-divergence shape for discrete distributions.

Parameters
1
1

Empirical P(Xˉn≥a)\mathbb{P}(\bar{X}_n \geq a) vs Cram\u00e9r Prediction

Compare the empirical tail probability of the sample mean (from Monte Carlo simulation) with the large deviations prediction e−nI(a)e^{-nI(a)}. Watch the log-probability become linear in nn with slope −I(a)-I(a).

Parameters
2
200

Quick Check

Which of the following is always true about the rate function I(x)I(x)?

I(x)≥0I(x) \geq 0 for all xx, with I(μ)=0I(\mu) = 0

I(x)I(x) is always symmetric about μ\mu

I(x)I(x) is always bounded

I(x)I(x) is always concave

Correction:
I(x)≥0I(x) \geq 0 for all xx, with I(μ)=0I(\mu) = 0

Since Λ(0)=0\Lambda(0) = 0 and Λ\Lambda is convex, the supremum I(x)=sup⁡θ{θx−Λ(θ)}≥0I(x) = \sup_\theta\{\theta x - \Lambda(\theta)\} \geq 0, with equality at x=μ=Λ′(0)x = \mu = \Lambda'(0).

Common Mistake: Cramér's Theorem Requires i.i.d. Samples

Mistake:

Applying Cramér's theorem to dependent sequences or non-identically distributed sums without checking the assumptions.

Correction:

Cramér's theorem as stated requires i.i.d. random variables. Extensions to weakly dependent sequences exist (Gärtner-Ellis theorem) but require the limit lim⁡n→∞1nΛSn(θ)\lim_{n \to \infty} \frac{1}{n}\Lambda_{S_n}(\theta) to exist and be differentiable, where Sn=∑i=1nXiS_n = \sum_{i=1}^n X_i. Markov chains satisfy this under mild conditions.

Definition:

Large Deviation Principle

A sequence of probability measures {μn}\{\mu_n\} on R\mathbb{R} satisfies a large deviation principle (LDP) with speed nn and rate function II if:

  1. Upper bound: For every closed set FF, lim sup⁡n→∞1nlog⁡μn(F)≤−inf⁡x∈FI(x)\limsup_{n \to \infty} \frac{1}{n}\log \mu_n(F) \leq -\inf_{x \in F} I(x).

  2. Lower bound: For every open set GG, lim inf⁡n→∞1nlog⁡μn(G)≥−inf⁡x∈GI(x)\liminf_{n \to \infty} \frac{1}{n}\log \mu_n(G) \geq -\inf_{x \in G} I(x).

  3. II is lower semicontinuous with compact level sets {x:I(x)≤α}\{x : I(x) \leq \alpha\} for all α\alpha.

Cramér's theorem states that P(Xˉn∈⋅)\mathbb{P}(\bar{X}_n \in \cdot) satisfies an LDP with rate function I(x)=Λ∗(x)I(x) = \Lambda^*(x).

Good Rate Function

A rate function I:R→[0,∞]I : \mathbb{R} \to [0, \infty] is called good if all its level sets {x:I(x)≤α}\{x : I(x) \leq \alpha\} are compact for every α≥0\alpha \geq 0. Cramér's rate function is always good when the MGF is finite in a neighborhood of zero.

Related: Rate Function (Fenchel-Legendre Transform), Large Deviation Principle

The Gärtner-Ellis Extension

When the XiX_i are not identically distributed or have weak dependence, one can still obtain an LDP if the limiting cumulant generating function Λ(θ)=lim⁡n→∞1nlog⁡E[eθSn]\Lambda(\theta) = \lim_{n \to \infty} \frac{1}{n}\log \mathbb{E}[e^{\theta S_n}] exists and is differentiable on its effective domain. This is the Gärtner-Ellis theorem, which reduces to Cramér's theorem in the i.i.d. case. It applies, for instance, to Markov chains and to sums with slowly varying distributions.

Key Takeaway

Cramér's theorem is the fundamental result of large deviations theory for i.i.d. sums: the probability of the sample mean exceeding a threshold a>μa > \mu decays as e−nI(a)e^{-nI(a)}, where I(a)=sup⁡θ{θa−log⁡E[eθX]}I(a) = \sup_\theta\{\theta a - \log \mathbb{E}[e^{\theta X}]\} is the Legendre-Fenchel transform of the log-MGF. The rate function II is convex, non-negative, and zero only at the true mean.

Prerequisites & NotationSanov's Theorem (Preview)