Chernoff Rate Functions as Convex Duals

From an Optimized Bound to a Rate Function

An exponential Markov bound starts with a choice of tilt $t\geq 0$: for a random variable $X$, a large value of $t$ places more weight on large values of $X$, while a small value places less. The Chernoff bound chooses the tilt that gives the strongest valid bound. The rate function packages that optimization as a function of the threshold. Its value measures the best exponential decay that this particular method certifies.

The log moment-generating function is the natural object for this optimization. Write $M_X(t)=E[e^{tX}]$ when this expectation is finite, and define $\Lambda(t)=\log M_X(t)$. At a threshold $x$, the quantity to maximize is $tx-\Lambda(t)$. It is affine in $x$ for each fixed $t$, and the supremum over admissible nonnegative $t$ gives the upper-tail rate.

Definition: Let $X$ be a real-valued random variable with $E[X]$ finite. Let $D=\{t\in\mathbb{R}:E[e^{tX}]<\infty\}$, and for $t\in D$ define $\Lambda(t)=\log E[e^{tX}]$. The upper-tail Chernoff rate function is $$ I_+(x)=\sup_{t\in D,\ t\geq 0}\{tx-\Lambda(t)\},\qquad x\in\mathbb{R}. $$

Because $0\in D$ and $\Lambda(0)=0$, the choice $t=0$ is always available and gives value zero. Thus $I_+(x)\geq 0$. The restriction $t\geq0$ matters: it makes this an upper-tail rate. The unrestricted convex conjugate, often written $\Lambda^*(x)=\sup_{t\in D}\{tx-\Lambda(t)\}$, allows negative as well as positive tilts. In general $I_+$ and $\Lambda^*$ are not the same function.

Why This Is a Convex Dual

For each admissible $t\geq0$, $tx-\Lambda(t)$ is a straight line as a function of $x$, with slope $t$. The rate is the pointwise supremum of those lines. This geometric description directly yields two useful properties.

Theorem: The upper-tail rate $I_+$ is convex and nondecreasing on $\mathbb{R}$, with values allowed in $[0,\infty]$. If $E[X]=\mu$ and $E[e^{tX}]<\infty$ for all $t$ in some interval $[0,\varepsilon)$, where $\varepsilon>0$, then $I_+(x)=0$ for every $x\leq\mu$.

Proof. Fix $x,y\in\mathbb{R}$ and $a\in[0,1]$. For every admissible $t\geq0$, $$ t(ax+(1-a)y)-\Lambda(t) =a\{tx-\Lambda(t)\}+(1-a)\{ty-\Lambda(t)\}. $$ The right side is at most $aI_+(x)+(1-a)I_+(y)$. Taking the supremum over $t$ proves $I_+(ax+(1-a)y)\leq aI_+(x)+(1-a)I_+(y)$, so $I_+$ is convex. If $x\leq y$, then $tx-\Lambda(t)\leq ty-\Lambda(t)$ for every admissible $t\geq0$. Taking suprema proves $I_+(x)\leq I_+(y)$, so $I_+$ is nondecreasing.

For $t\geq0$, Jensen’s inequality gives $E[e^{tX}]\geq e^{tE[X]}=e^{t\mu}$, hence $\Lambda(t)\geq t\mu$. If $x\leq\mu$, it follows that $tx-\Lambda(t)\leq t(x-\mu)\leq0$ for every admissible $t\geq0$. Since $t=0$ gives zero, the supremum is exactly zero. $\square$

The derivative of the log-MGF locates an interior optimum. When the MGF is finite on an open interval around a value $t$, differentiation under the expectation is valid there, and $$ \Lambda'(t)=\frac{E[Xe^{tX}]}{E[e^{tX}]}. $$ Thus the stationary-point equation for $tx-\Lambda(t)$ is $\Lambda'(t)=x$. If $\Lambda$ is strictly convex on the positive part of its domain, this equation has at most one solution there; when a solution exists, it is the unique interior maximizer. The equation does not guarantee that a solution exists: the supremum can instead be approached at the boundary of the MGF domain.

Worked Example: A Normal Distribution

Let $X\sim N(\mu,\sigma^2)$, with $\sigma^2>0$. Its log-MGF is $\Lambda(t)=\mu t+\sigma^2t^2/2$, finite for every real $t$. For a threshold $x>\mu$, maximize $$ tx-\Lambda(t)=t(x-\mu)-\frac{\sigma^2t^2}{2},\qquad t\geq0. $$

Differentiating with respect to $t$ gives $x-\mu-\sigma^2t$, which vanishes at $t_x=(x-\mu)/\sigma^2>0$. The second derivative is $-\sigma^2<0$, so this is the maximum. Substitution gives $$ I_+(x)=\frac{x-\mu}{\sigma^2}(x-\mu)-\frac{\sigma^2}{2}\left(\frac{x-\mu}{\sigma^2}\right)^2 =\frac{(x-\mu)^2}{2\sigma^2}. $$ For $x\leq\mu$, the theorem gives $I_+(x)=0$. In particular, the rate is zero at the mean and rises quadratically above it.

Worked Example: Rademacher Distribution

Let $X$ take the values $1$ and $-1$, each with probability $1/2$. Then $E[X]=0$, $M_X(t)=(e^t+e^{-t})/2=\cosh t$, and $\Lambda(t)=\log\cosh t$. For $0<x<1$, the derivative equation is $\tanh t=x$, giving $t_x=\operatorname{atanh}(x)=\tfrac12\log\{(1+x)/(1-x)\}$. Since $\Lambda''(t)=1/\cosh^2(t)>0$, the objective is strictly concave and this stationary point is its maximum.

Using $\cosh(\operatorname{atanh}(x))=1/\sqrt{1-x^2}$, the rate is $$ I_+(x)=x\operatorname{atanh}(x)+\frac12\log(1-x^2),\qquad 0<x<1. $$ At $x=1$, the objective is $t-\log\cosh t$, which tends to $\log 2$ as $t\to\infty$, so $I_+(1)=\log 2$. For $x>1$, $tx-\log\cosh t$ tends to infinity as $t\to\infty$, so $I_+(x)=\infty$. For $x\leq0$, the theorem gives zero.

For a numerical check, take $x=1/2$. Then $t_x=\tfrac12\log 3\approx0.5493$, and $\log\cosh(t_x)=-\tfrac12\log(3/4)\approx0.1438$. Therefore $$ I_+(1/2)=\frac12(0.5493)-0.1438\approx0.1308. $$

When the Optimizer Is Described Implicitly

A closed-form expression for the optimizing tilt is not always available. The derivative equation still identifies the rate exactly when the log-MGF is differentiable and the corresponding tilt lies in the interior of its domain. The uniform distribution gives a concrete example.

Worked Example: Uniform Distribution on an Interval

Let $X$ be uniform on $[-1,1]$. Its mean is zero, and for $t>0$, $$ M_X(t)=\frac12\int_{-1}^{1}e^{tx}\,dx=\frac{e^t-e^{-t}}{2t}=\frac{\sinh t}{t}, \qquad \Lambda(t)=\log\left(\frac{\sinh t}{t}\right). $$ The MGF is finite for every real $t$. Differentiating for $t>0$ gives $\Lambda'(t)=\coth t-1/t$. For $0<x<1$, the rate is evaluated at the positive solution $t_x$ to $\coth t_x-1/t_x=x$. There need not be a simple closed form for $t_x$, but the solution is unique: $\Lambda''(t)$ is the variance under the exponentially tilted distribution, which is strictly positive because that distribution is not concentrated at one point.

Choose $t=\log 3$. Then $\coth(\log 3)=(3^2+1)/(3^2-1)=5/4$. The corresponding threshold is $$ x=\Lambda'(\log 3)=\frac54-\frac{1}{\log 3}\approx0.3398. $$ Because this threshold is exactly $\Lambda'(\log 3)$, strict convexity ensures that $\log 3$ is the maximizing tilt. Also, $\sinh(\log 3)=4/3$, so $$ I_+(x)=x\log 3-\log\left(\frac{4}{3\log 3}\right) =\frac54\log 3-1-\log\left(\frac{4}{3\log 3}\right) \approx0.1795. $$ This example shows how to compute a rate even when the optimizer must be specified by an equation rather than an elementary formula.

The Rate Gives a Chernoff Exponent

The rate function is directly connected to a finite-sample tail bound. Let $X_1,\ldots,X_n$ be independent and identically distributed copies of $X$, and assume the MGF is finite at each tilt being used. For fixed $t\geq0$, the event $\sum_{i=1}^nX_i\geq nx$ implies $e^{t\sum_iX_i}\geq e^{tnx}$. Markov’s inequality and independence therefore give $$ P\left(\frac1n\sum_{i=1}^nX_i\geq x\right) \leq e^{-tnx}E\left[e^{t\sum_{i=1}^nX_i}\right] =\exp\{-n(tx-\Lambda(t))\}. $$

This inequality holds for every admissible $t\geq0$. Taking the infimum of its right side over those tilts yields the rate-form bound $$ P\left(\frac1n\sum_{i=1}^nX_i\geq x\right)\leq e^{-nI_+(x)}. $$ If $I_+(x)=\infty$, the right side is interpreted as zero; this follows by applying the bound at every admissible tilt and letting $tx-\Lambda(t)$ increase without bound. If $I_+(x)=0$, the inequality is valid but gives only the uninformative upper bound one.

For example, if $X_1,\ldots,X_n$ are independent $N(0,1)$ variables, then at threshold $x=1$ the normal calculation gives $I_+(1)=1/2$. Hence the sample mean satisfies $P(\overline X_n\geq1)\leq e^{-n/2}$. The expression $I_+(1)$ is the optimized exponent in this bound; it is not itself the probability of the event.

Common Mistake: Using the Wrong Dual

A common mistake is to use the unrestricted supremum over all real $t$ when the target is an upper-tail bound. Negative tilts emphasize small, rather than large, values; they belong to a lower-tail calculation. For example, for $X\sim N(\mu,\sigma^2)$ and $x<\mu$, the upper-tail rate is $I_+(x)=0$, because the allowed tilts satisfy $t\geq0$. The unrestricted conjugate is instead $(x-\mu)^2/(2\sigma^2)>0$. That positive value comes from a negative optimizing tilt, so it cannot be used as the upper-tail Chernoff exponent. Always check the sign restriction in the supremum against the direction of the event.

Key takeaway: The upper-tail rate is the supremum of $tx-\Lambda(t)$ over nonnegative tilts where the MGF is finite. It is a convex, nondecreasing function, and it gives the optimized exponent in a Chernoff bound. An interior optimizer solves $\Lambda'(t)=x$; domain boundaries and support endpoints require separate attention.

Check Your Understanding

Use the definitions and derivations above to answer the following.

Why does restricting the supremum to $t\geq0$ make $I_+$ an upper-tail rate rather than an unrestricted convex conjugate?
For $X\sim N(2,9)$, calculate $I_+(5)$ and state the optimizing tilt.
For a Rademacher random variable, what happens to $I_+(x)$ at $x=1$ and for $x>1$? Explain using the supremum.
For the uniform distribution on $[-1,1]$, write the derivative equation that determines the optimizing tilt at a threshold $0<x<1$.
Does a positive value of $I_+(x)$ give the exact probability of an upper-tail event? State what it gives instead.