Hoeffding's lemma

Let X be any real-valued random variable such that ${\displaystyle a\leq X\leq b}$ almost surely, i.e. with probability one. Then, for all ${\displaystyle \lambda \in \mathbb {R} }$,

${\displaystyle \mathbb {E} \left[e^{\lambda X}\right]\leq \exp {\Big (}\lambda \mathbb {E} [X]+{\frac {\lambda ^{2}(b-a)^{2}}{8}}{\Big )},}$

or equivalently,

${\displaystyle \mathbb {E} \left[e^{\lambda (X-\mathbb {E} [X])}\right]\leq \exp {\Big (}{\frac {\lambda ^{2}(b-a)^{2}}{8}}{\Big )}.}$

Without loss of generality, by replacing ${\displaystyle X}$ by ${\displaystyle X-\mathbb {E} [X]}$, we can assume ${\displaystyle \mathbb {E} [X]=0}$, so that ${\displaystyle a\leq 0\leq b}$.

Since ${\displaystyle e^{\lambda x}}$ is a convex function of ${\displaystyle x}$, we have that for all ${\displaystyle x\in [a,b]}$,

${\displaystyle e^{\lambda x}\leq {\frac {b-x}{b-a}}e^{\lambda a}+{\frac {x-a}{b-a}}e^{\lambda b}}$

So,

${\displaystyle {\begin{aligned}\mathbb {E} \left[e^{\lambda X}\right]&\leq {\frac {b-\mathbb {E} [X]}{b-a}}e^{\lambda a}+{\frac {\mathbb {E} [X]-a}{b-a}}e^{\lambda b}\\&={\frac {b}{b-a}}e^{\lambda a}+{\frac {-a}{b-a}}e^{\lambda b}\\&=e^{L(\lambda (b-a))},\end{aligned}}}$

where ${\displaystyle L(h)={\frac {ha}{b-a}}+\ln(1+{\frac {a-e^{h}a}{b-a}})}$. By computing derivatives, we find

${\displaystyle L(0)=L'(0)=0}$ and ${\displaystyle L''(h)=-{\frac {abe^{h}}{(b-ae^{h})^{2}}}}$.

From the AMGM inequality we thus see that ${\displaystyle L''(h)\leq {\frac {1}{4}}}$ for all ${\displaystyle h}$, and thus, from Taylor's theorem, there is some ${\displaystyle 0\leq \theta \leq 1}$ such that

${\displaystyle L(h)=L(0)+hL'(0)+{\frac {1}{2}}h^{2}L''(h\theta )\leq {\frac {1}{8}}h^{2}.}$

Thus, ${\displaystyle \mathbb {E} \left[e^{\lambda X}\right]\leq e^{{\frac {1}{8}}\lambda ^{2}(b-a)^{2}}}$.

• Hoeffding's inequality
• Bennett's inequality