Hoeffding's Lemma for Bounded Variables

Why a Bounded Range Controls the MGF

A random variable confined to a finite interval cannot make arbitrarily large deviations. Hoeffding’s lemma turns that basic fact into a precise statement about its moment-generating function (MGF). The result is useful because an MGF bound can be inserted into exponential Markov arguments, while the lemma itself requires neither a particular distribution nor independence.

The centering is essential: the lemma bounds the MGF of a variable with mean zero, and its bound depends only on the length of the interval, not on where the interval lies. We first state the result in a form that also applies to a noncentered variable after subtracting its mean.

Theorem (Hoeffding’s lemma): Let $X$ be a random variable with $a\leq X\leq b$ almost surely, where $a$ and $b$ are finite, and let $\mu=E[X]$. Then, for every $t\in\mathbb{R}$, $$ E\!\left[e^{t(X-\mu)}\right]\leq \exp\!\left(\frac{t^2(b-a)^2}{8}\right). $$ In particular, if $E[X]=0$, then $E[e^{tX}]\leq \exp(t^2(b-a)^2/8)$. If $b>a$, equality holds only for $t=0$; if $b=a$, the centered variable is zero almost surely and equality holds for every $t$.

Reducing to a Two-Point Bound

Set $Z=X-\mu$. Then $E[Z]=0$, and $Z$ lies in the interval $[A,B]=[a-\mu,b-\mu]$, whose length is $d=b-a$. If $d>0$, the mean-zero condition implies $A\leq 0\leq B$. The first step of the proof uses convexity to compare the exponential at each point in this interval with the line joining its endpoint values.

For any real $t$, the function $z\mapsto e^{tz}$ is convex. Therefore, for $A\leq z\leq B$, $$ e^{tz}\leq \frac{B-z}{d}e^{tA}+\frac{z-A}{d}e^{tB}. $$ Taking expectations and using $E[Z]=0$ gives $$ E[e^{tZ}] \leq \frac{B}{d}e^{tA}+\frac{-A}{d}e^{tB}. $$ When $A<0<B$, write $p=-A/d$, so $0<p<1$, $A=-pd$, and $B=(1-p)d$. With $u=td$, the endpoint bound becomes $$ E[e^{tZ}]\leq (1-p)e^{-pu}+p e^{(1-p)u}. $$ This is the MGF of a centered two-point variable that places probabilities $1-p$ and $p$ at the two endpoints. Thus, among the distributions supported on this interval with mean zero, the endpoint expression supplies an upper bound. It remains to control that expression uniformly in $p$.

Bounding the Endpoint MGF

For $0<p<1$, define $$ h(u)=\log\!\left((1-p)e^{-pu}+p e^{(1-p)u}\right). $$ To calculate its curvature, let $$ r(u)=\frac{p e^{(1-p)u}}{(1-p)e^{-pu}+p e^{(1-p)u}}. $$ Differentiating gives $h'(u)=r(u)-p$ and $h''(u)=r(u)(1-r(u))$. Since $0<r(u)<1$, the product is at most $1/4$. Also $h(0)=0$ and $h'(0)=0$.

Curvature bound: For all real $u$, $$ h''(u)\leq \frac14,\qquad h(0)=h'(0)=0, $$ and consequently $h(u)\leq u^2/8$.

Here is the complete integration step, including negative $u$. For $u\geq 0$, Taylor’s formula with an integral remainder gives $h(u)=\int_0^u (u-s)h''(s)\,ds$. The integrand’s weight $u-s$ is nonnegative, so $$ h(u)\leq \frac14\int_0^u(u-s)\,ds=\frac{u^2}{8}. $$ For $u<0$, the corresponding formula is $h(u)=\int_u^0(s-u)h''(s)\,ds$. Its weight $s-u$ is nonnegative, and hence $$ h(u)\leq \frac14\int_u^0(s-u)\,ds=\frac{u^2}{8}. $$ In both cases, exponentiation gives $(1-p)e^{-pu}+p e^{(1-p)u}\leq e^{u^2/8}$. Substituting $u=td$ into the endpoint bound proves Hoeffding’s lemma when $A<0<B$.

If $A=0$, then $Z\geq 0$ and $E[Z]=0$, which forces $Z=0$ almost surely. If $B=0$, the same reasoning applied to $-Z$ gives $Z=0$ almost surely. The desired inequality holds in either case. If $d=0$, $X$ is constant and $X-\mu=0$ almost surely, so the inequality holds with equality for every $t$. This covers the boundary cases as well.

Worked Examples

Worked Example: A Centered Bernoulli Variable

Let $I$ have a Bernoulli distribution with $P(I=1)=1/4$, and set $Z=I-1/4$. Then $E[Z]=0$, and $Z$ takes values $-1/4$ and $3/4$, so its range has length $1$. At $t=2$, $$ E[e^{2Z}] =\frac34e^{-1/2}+\frac14e^{3/2} \approx \frac34(0.60653)+\frac14(4.48169) \approx 1.57532. $$ Hoeffding’s bound is $$ \exp\!\left(\frac{2^2(1)^2}{8}\right)=e^{1/2}\approx 1.64872. $$ Thus $E[e^{2Z}]\approx1.57532\leq1.64872$, as asserted. The bound applies without requiring the Bernoulli distribution to be symmetric.

Worked Example: A Symmetric Two-Point Variable

Let $Z$ equal $-1$ and $1$, each with probability $1/2$. Its mean is zero and its range has length $2$. Direct calculation gives $$ E[e^{tZ}]=\frac{e^{-t}+e^t}{2}=\cosh(t). $$ Hoeffding’s lemma therefore gives $\cosh(t)\leq e^{t^2/2}$. At $t=1$, the two sides are approximately $1.54308$ and $1.64872$, respectively. At $t=0$, both sides equal $1$. At every nonzero $t$, the inequality is strict; symmetry does not make the bound an equality away from zero.

Worked Example: A Centered Uniform Variable

Let $X$ be uniform on $[2,6]$. Its mean is $\mu=4$, so $Z=X-\mu$ is uniform on $[-2,2]$, an interval of length $4$. At $t=1/2$, direct integration gives $$ E[e^{Z/2}] =\frac14\int_{-2}^{2}e^{z/2}\,dz =\frac{e-e^{-1}}{2} =\sinh(1) \approx1.17520. $$ The lemma gives the upper bound $$ \exp\!\left(\frac{(1/2)^2(4)^2}{8}\right)=e^{1/2}\approx1.64872. $$ The direct value is below the bound. The calculation also illustrates why the interval’s location is irrelevant: the original variable lies in $[2,6]$, but the MGF bound is for $X-4$, and depends only on the range length $6-2=4$.

Equality and Sharpness

When $b>a$, the lemma’s inequality is strict for every $t\ne0$. To see why, first suppose $A<0<B$. For $0<p<1$, $r(u)$ is strictly between zero and one, and $r(u)=1/2$ can hold at most at one value of $u$. Thus $h''(u)=r(u)(1-r(u))$ is strictly below $1/4$ except possibly at one point. The integral remainder for any nonzero $u$ has a positive weight over an interval of positive length, so $h(u)<u^2/8$. If instead one endpoint of the centered interval is zero, the centered variable is constant zero and its MGF is $1<e^{t^2d^2/8}$ for $d>0$, $t\ne0$. Equality at $t=0$ follows directly because both sides then equal $1$. When $b=a$, the centered variable is zero almost surely, giving equality for all $t$.

Strict inequality for nonzero $t$ does not mean the constant $1/8$ can be improved. For the symmetric two-point variable taking values $-d/2$ and $d/2$ with equal probability, the MGF is $\cosh(td/2)$. As $t$ tends to zero, $$ \frac{\log \cosh(td/2)}{t^2d^2}\longrightarrow\frac18. $$ This follows, for example, from $\log\cosh(x)=x^2/2+o(x^2)$ as $x\to0$. If $1/8$ were replaced by any smaller universal coefficient, this limit would contradict the proposed bound for sufficiently small nonzero $t$. The constant is therefore optimal over all centered distributions with a given range length, even though the bound is not attained for nonzero $t$ when the range has positive length.

Common Pitfall and Use

Using the endpoints themselves as the centered support. If $X$ lies in $[a,b]$, its mean need not be zero. Apply the lemma to $X-E[X]$, whose range is $[a-E[X],b-E[X]]$; the length remains $b-a$.
Dropping the square on $t$. The bound must hold for positive and negative $t$. Its exponent contains $t^2$, so it is nonnegative in either direction.
Interpreting “sharp” as equality at a nonzero argument. The constant $1/8$ is optimal uniformly, but for a nondegenerate bounding interval the inequality is strict whenever $t\ne0$.

The practical value of the lemma is that it replaces a distribution-specific MGF calculation with a bound determined only by the support width. In an exponential Markov argument, a centered bounded summand can therefore be controlled using its interval length, even when its exact distribution is inconvenient. This tutorial establishes the single-variable bound; combining such bounds for sums requires accounting for independence and is a separate step.

Check Your Understanding

Use the centering, interval length, and equality discussion to answer these questions.

If $X$ lies in $[3,9]$, what range length appears in the bound for $E[e^{t(X-E[X])}]$?
Why does the proof compare the MGF with that of a two-point distribution at the interval endpoints?
For a centered variable in an interval of positive length, at which value of $t$ does equality necessarily hold?
Why does strict inequality at every nonzero $t$ not allow the coefficient $1/8$ to be reduced?
If a centered variable is nonnegative almost surely, what can be concluded about the variable, and why?