= Hoeffding lemma
{c}
{title2=$\log\mathbb E e^{\lambda(X-\mathbb EX)}\leq\lambda^2(b-a)^2/8$}
{wiki=Hoeffding's_lemma}
= Hoeffding's lemma
{c}
{synonym}
The <Hoeffding lemma> controls the entire centered <moment-generating function> using only an <interval> width. For an <essentially bounded> real <random variable> $X$ with finite deterministic bounds $a\leq X\leq b$ <almost surely>, every real $\lambda$ satisfies
$$
\boxed{\psi(\lambda):=\log\mathbb E e^{\lambda(X-\mathbb EX)}\leq\frac{\lambda^2(b-a)^2}{8}.}
$$
Equivalently, $\mathbb E e^{\lambda(X-\mathbb EX)}\leq e^{\lambda^2(b-a)^2/8}$. This single-<random variable> statement needs no <independence> assumption; <independence> enters when applying it to the factors for a <sum> in the <Hoeffding inequality>. Both signs of $\lambda$ are allowed, and equality holds at $\lambda=0$ or when $a=b$.<CS229 Supplemental Lecture notes/Hoeffding’s inequality>[§3, p. 6, lemma 5: all-real-parameter moment-generating function bound]{ref}
In the convention $\log\mathbb E e^{\lambda Y}\leq\lambda^2\sigma^2/2$ for a centered <sub-Gaussian random variable> $Y$, the <Hoeffding lemma> supplies $\sigma^2=(b-a)^2/4$. This upper parameter need not equal the actual <variance>. For a <Bernoulli random variable> $B$ of success <probability> $p$,
$$
\log\mathbb E e^{\lambda(B-p)}=\log(1-p+pe^\lambda)-p\lambda\leq\lambda^2/8.
$$
The actual <variance> is $p(1-p)$, whereas the supplied parameter is $1/4$ for every $p$. This explains part of the conservatism visible in <Hoeffding sample size for Bernoulli frequencies>.
\Image[/hoeffding-bounded-interval-exponential-tilt.png]
{title=<Exponential tilting> changes the weights but preserves the bounded <interval>}
{description=The original three-point model has $X=-2,0,2$ with <probabilities> $1/4,1/2,1/4$ and <mean> zero. Left: tilted masses proportional to $\mathbb P(X=x)e^{\lambda x}$ for $\lambda=-1,0,1$ stay within $[-2,2]$. Right: its <cumulant-generating function> $\psi(\lambda)=2\log\cosh\lambda$ stays below the <Hoeffding lemma> bound $2\lambda^2$. Its tilted <variance> is $\psi''(\lambda)=2/\cosh^2\lambda\leq2$, smaller than the general width-only ceiling four.}
A short proof exposes why the constant is $1/8$. Put $Y=X-\mathbb EX$ and define <exponential tilting> by
$$
d\mathbb P_\lambda=e^{\lambda Y-\psi(\lambda)}d\mathbb P.
$$
The tilted <probability measure> has the same <interval> of possible values, and differentiating the <cumulant-generating function> gives $\psi''(\lambda)=\operatorname{Var}_{\mathbb P_\lambda}(Y)$. Boundedness justifies these <derivatives> for every finite $\lambda$. Under any such tilted law, <Popoviciu's inequality on variances> gives $\psi''(\lambda)\leq(b-a)^2/4$: the <variance> is no larger than the <expected value> of the squared distance from the <interval> midpoint, itself at most $(b-a)^2/4$. Since $\psi(0)=\psi'(0)=0$, the integral form of <Taylor's theorem> yields
$$
\psi(\lambda)=\lambda^2\int_0^1(1-s)\psi''(s\lambda)\,ds\leq\lambda^2(b-a)^2/8.
$$
This expression handles either sign of $\lambda$ without changing the argument.
The constant $1/8$ cannot be reduced uniformly over all <essentially bounded> real <random variables>. Equal endpoint <probabilities> at $a$ and $b$ give $Y=\pm(b-a)/2$, a scaled <Rademacher random variable>, and
$$
\lim_{\lambda\to0}\frac{\log\mathbb E e^{\lambda Y}}{\lambda^2}=\frac{\operatorname{Var}(Y)}2=\frac{(b-a)^2}{8}.
$$
Thus the sharpness is already forced near zero by the <variance>; the bound need not be equality at nonzero parameters for a particular <probability distribution>.
Back to article page
