Exponential Tilting and Chernoff Bound Sharpness

Why Reweight a Probability Distribution?

A Chernoff bound chooses an exponential parameter to make a rare event less costly to bound. There is a second interpretation: the parameter changes the probability weights themselves. Under the resulting tilted distribution, values near the rare-event threshold can become typical. This gives a way to understand both the optimizing parameter and when the Chernoff exponent describes the true rate of decay.

We develop this idea for a real-valued random variable $X$ whose moment-generating function is finite near the parameter of interest. For sums of independent, identically distributed variables, we will show that tilting toward a threshold makes the sample average concentrate near that threshold. A change of measure then gives a matching lower bound on the exponential scale.

Definition and Basic Properties of the Tilt

Definition: Let $X$ have moment-generating function $M(t)=E[e^{tX}]$, finite on an open interval containing $t$. Define its cumulant-generating function $K(t)=\log M(t)$. The exponentially tilted distribution at $t$ is the probability measure $P_t$ defined by $$ \frac{dP_t}{dP}(x)=e^{tx-K(t)}. $$ Equivalently, for any measurable set $A$, $P_t(A)=E[e^{tX-K(t)}\mathbf{1}_{\{X\in A\}}]$.

The density ratio is positive and has expectation one, since $E[e^{tX-K(t)}]=e^{-K(t)}M(t)=1$; thus it defines a probability measure. For $t>0$, values of $X$ with larger $x$ receive greater relative weight. For $t<0$, smaller values receive greater relative weight. The normalizing term $K(t)$ ensures that the new weights sum or integrate to one.

When the moment-generating function is finite on an open interval around $t$, differentiation under the expectation gives $K'(t)=E_t[X]$ and $K''(t)=\operatorname{Var}_t(X)$. The open-interval condition justifies the derivatives: in a smaller neighborhood of $t$, factors $|X|$ and $X^2$ multiplied by $e^{tX}$ are bounded by constant multiples of exponentials at nearby parameters, whose expectations are finite. In particular, the tilted mean is the derivative of the cumulant-generating function, and the tilted variance is its second derivative.

For independent $X_1,\ldots,X_n$ with a common cumulant-generating function $K$, tilting their joint distribution by $e^{tS_n-nK(t)}$, where $S_n=\sum_{i=1}^n X_i$, preserves independence: the joint density ratio factors as $\prod_{i=1}^n e^{tX_i-K(t)}$. Each variable then has distribution $P_t$, so under the tilted joint law, $E_t[S_n]=nK'(t)$ and $\operatorname{Var}_t(S_n)=nK''(t)$.

Worked Examples: What the Optimizing Tilt Does

Worked Example: A Binomial Upper Tail

Let $X_1,\ldots,X_n$ be independent Bernoulli variables with success probability $p$, where $0<p<1$. Write $S_n=\sum_i X_i$, and consider a threshold $nq$ with $p<q<1$. For one variable, $$ K(t)=\log(1-p+pe^t), \qquad K'(t)=\frac{pe^t}{1-p+pe^t}. $$

The optimizing parameter solves $K'(t)=q$. Rearranging gives $$ q(1-p+pe^t)=pe^t,\qquad e^t=\frac{q(1-p)}{p(1-q)},\qquad t_*=\log\!\left(\frac{q(1-p)}{p(1-q)}\right)>0. $$

Under the tilt, the success probability is $P_{t_*}(X_i=1)=pe^{t_*}/(1-p+pe^{t_*})=q$. Thus the rare event of an empirical success fraction at least $q$ under the original law is centered at fraction $q$ under the tilted law. Substitution into the rate gives $$ t_*q-K(t_*)=q\log\!\left(\frac{q}{p}\right)+(1-q)\log\!\left(\frac{1-q}{1-p}\right). $$ The Chernoff bound is therefore $P(S_n\ge nq)\le \exp[-n\{q\log(q/p)+(1-q)\log((1-q)/(1-p))\}]$.

Worked Example: A Poisson Sum

Let $X_i$ be independent Poisson variables with mean $\lambda>0$. Their cumulant-generating function is $K(t)=\lambda(e^t-1)$. For a threshold $na$, where $a>\lambda$, the optimizer solves $K'(t)=\lambda e^t=a$, so $t_*=\log(a/\lambda)>0$. The tilted variable is Poisson with mean $\lambda e^{t_*}=a$: multiplying its mass at $k$ by $e^{t_*k-K(t_*)}$ changes it to $$ e^{-\lambda}\frac{\lambda^k}{k!}e^{t_*k-\lambda(e^{t_*}-1)} =e^{-a}\frac{a^k}{k!}. $$

The rate is $t_*a-K(t_*)=a\log(a/\lambda)-a+\lambda$, giving $P(S_n\ge na)\le \exp[-n\{a\log(a/\lambda)-a+\lambda\}]$. Under the tilted law, the sum has mean $na$; the threshold is no longer an atypically high value.

Worked Example: An Exponential Sum

Let $X_i$ be independent exponential variables with rate $1$, so each has density $e^{-x}$ for $x\ge0$. For $t<1$, $K(t)=-\log(1-t)$. For $a>1$, solving $K'(t)=1/(1-t)=a$ gives $t_*=1-1/a$, which lies between zero and one. The tilted density is $$ e^{t_*x-K(t_*)}e^{-x} =\frac{1}{a}e^{-x/a},\qquad x\ge0, $$ an exponential density with mean $a$. The rate is $t_*a-K(t_*)=a-1-\log a$, and hence the Chernoff bound is $P(S_n\ge na)\le e^{-n(a-1-\log a)}$. The tilt has increased the mean from $1$ to exactly the threshold per summand, $a$.

An Exact Change-of-Measure Identity

The exponential Markov inequality gives an upper bound by discarding a factor no greater than one. The change-of-measure identity displays that factor explicitly. Let $S_n$ be a sum of independent, identically distributed variables with cumulant-generating function $K$, and let $P_t$ denote the joint tilted law. Since $dP/dP_t=\exp(-tS_n+nK(t))$, for $t>0$,

P(S_n\ge na) =e^{nK(t)-tna} E_t\!\left[e^{-t(S_n-na)}\mathbf{1}_{\{S_n\ge na\}}\right].

On the event inside the expectation, $S_n-na\ge0$, so the factor $e^{-t(S_n-na)}$ is at most one. Also, the indicator is at most one. Dropping both gives $P(S_n\ge na)\le e^{-n(ta-K(t))}$, the Chernoff bound for this $t$. At an optimizing $t$, the tilt centers $S_n$ at $na$; the remaining expectation accounts for how much probability lies above the threshold and how far above it typical tilted values lie.

When the Chernoff Exponent Is Sharp

Theorem: Suppose $X_1,X_2,\ldots$ are independent and identically distributed, $K(t)=\log E[e^{tX_1}]$ is finite on an open interval containing $0$, and $K$ is twice differentiable on an open interval containing $t_a>0$. Suppose $K'(t_a)=a$, $0<K''(t_a)<\infty$, and for all sufficiently small $\delta>0$ there is $t_{a+\delta/2}>0$ in that interval such that $K'(t_{a+\delta/2})=a+\delta/2$. Then $$ \lim_{n\to\infty}\frac{1}{n}\log P(S_n\ge na) =-\{t_a a-K(t_a)\}. $$

The statement says that the optimized Chernoff bound has the correct exponential decay rate. It does not assert that the bound equals the tail probability, or that their ratio tends to one.

Proof. Set $I(a)=t_a a-K(t_a)$. The exponential Markov inequality at $t_a$ gives $P(S_n\ge na)\le e^{-nI(a)}$. Thus the limit superior of $n^{-1}\log P(S_n\ge na)$ is at most $-I(a)$.

For a lower bound, fix a sufficiently small $\delta>0$, set $b=a+\delta/2$, and choose $t_b>0$ with $K'(t_b)=b$. Under the joint tilt at $t_b$, the sample average $S_n/n$ has mean $b$ and variance $K''(t_b)/n$. Chebyshev's inequality therefore gives $$ P_{t_b}\!\left(\left|S_n/n-b\right|\le\delta/2\right) \ge 1-\frac{4K''(t_b)}{n\delta^2}\longrightarrow 1. $$ This event is contained in $\{na\le S_n\le n(a+\delta)\}$. Reversing the change of measure on this interval, where $S_n\le n(a+\delta)$, yields $$ P(S_n\ge na) \ge \exp\!\left(nK(t_b)-nt_b(a+\delta)\right) P_{t_b}\!\left(na\le S_n\le n(a+\delta)\right). $$ Consequently, for each fixed $\delta$, $$ \liminf_{n\to\infty}\frac1n\log P(S_n\ge na) \ge -\{t_b b-K(t_b)\}-t_b\delta/2. $$ As $\delta$ decreases to zero, $b$ decreases to $a$, and $t_b$ approaches $t_a$ by continuity of the inverse relation $K'(t_b)=b$ when $K''(t_a)>0$. The right-hand side therefore tends to $-I(a)$. The lower and upper limits agree, proving the claim. $\square$

The proof uses concentration under a tilt slightly beyond the target, at $b=a+\delta/2$. This places almost all tilted probability in a narrow interval that lies above the original threshold. Reversing the change of measure on that interval costs an exponential factor; as the interval narrows, that cost approaches the Chernoff rate at $a$.

Common Pitfall: Sharp Rate Is Not Exact Equality

A common mistake is to say that the tilted distribution makes the Chernoff bound equal to the tail probability. It does not. The exact identity contains the factor $E_t[e^{-t(S_n-na)}\mathbf{1}_{\{S_n\ge na\}}]$, which is generally less than one and can depend on $n$. The theorem establishes that its contribution to the logarithm, divided by $n$, does not change the limiting rate under the stated assumptions. It does not determine a finite-sample correction or a relative-error approximation.

The distinction matters in practice: a Chernoff bound may correctly capture how quickly a tail decays with sample size while still being numerically conservative at a particular $n$. Exponential tilting explains the exponent and identifies where rare-event probability is concentrated under changed weights; it is not, by itself, a claim of exact tail calculation.

Check Your Understanding

Use the change-of-measure interpretation and the conditions in the theorem to answer these questions.

For a tilt parameter $t>0$, which values of $X$ receive larger relative weight, and what role does $K(t)$ play?
For a sum of Bernoulli variables with success probability $p$, what success probability does the optimizing tilt produce at a threshold fraction $q>p$?
In the exact change-of-measure identity, which factor is discarded to obtain the Chernoff upper bound?
Why does the proof of sharpness use a tilted mean $a+\delta/2$, rather than tilting exactly at $a$?
What does sharpness on the exponential scale establish, and what does it not establish about the finite-sample bound?