This articlerelies largely or entirely on asingle source. Relevant discussion may be found on thetalk page. Please helpimprove this article byintroducing citations to additional sources. Find sources: "Hoeffding's lemma" – news ·newspapers ·books ·scholar ·JSTOR(March 2024)

Inprobability theory,Hoeffding's lemma is aninequality that bounds themoment-generating function of anyboundedrandom variable,^[1] implying that such variables aresubgaussian. It is named after theFinnish–Americanmathematical statisticianWassily Hoeffding.

The proof of Hoeffding's lemma usesTaylor's theorem andJensen's inequality. Hoeffding's lemma is itself used in the proof ofHoeffding's inequality as well as the generalizationMcDiarmid's inequality.

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

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

or equivalently,

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

The following proof is direct but somewhat ad-hoc. Another proof usesexponential tilting;^{[2]: Lemma 2.2} proofs with a slightly worse constant are also available using symmetrization.^[3]

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\le 0\le 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}\le \frac{b-x}{b-a}{e}^{\lambda a}+\frac{x-a}{b-a}{e}^{\lambda b}}$

So,

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^{\prime }(0)=0}$ and${\displaystyle L^{″}(h)=-\frac{ab{e}^h}{(b-a{e}^h{)}^2}}$.

From theAMGM inequality we thus see that${\displaystyle L^{″}(h)\le \frac{1}{4}}$ for all${\displaystyle h}$, and thus, fromTaylor's theorem, there is some${\displaystyle 0\le \theta \le 1}$ such that

${\displaystyle L(h)=L(0)+h{L}^{\prime }(0)+\frac{1}{2}{h}^2{L}^{″}(h\theta )\le \frac{1}{8}{h}^2.}$

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

• Hoeffding's inequality
• Bennett's inequality

Thisprobability-related article is astub. You can help Wikipedia byexpanding it.

• v
• t
• e

• Probabilistic inequalities
• Probability stubs

• Articles with short description
• Short description matches Wikidata
• Articles needing additional references from March 2024
• All articles needing additional references
• All stub articles