# Does the proof of Hoeffding's lemma use Jensen's inequality?

From Wikipedia

The proof of Hoeffding's lemma uses Taylor's theorem and Jensen's inequality.

Let $X$ be any real-valued random variable with expected value $E[X] = 0$ and such that$a ≤ X ≤ b$ almost surely. Then, for all $λ ∈ R$, $$\mathbf{E} \left[ e^{\lambda X} \right] \leq \exp \left( \frac{\lambda^2 (b - a)^2}{8} \right).$$

Proof of the lemma

Since $e^{\lambda x}$ is a convex function, we have $$e^{\lambda x}\leq \frac{b-x}{b-a}e^{\lambda a}+\frac{x-a}{b-a}e^{\lambda b} \forall a\leq x\leq b$$ So, $\mathbf{E}\left[e^{\lambda X}\right] \leq \frac{b-EX}{b-a}e^{\lambda a}+\frac{EX-a}{b-a}e^{\lambda b}$.

Let $h=\lambda(b-a), p=\frac{-a}{b-a}$ and $L(h)=-hp+ln(1-p+pe^h)$

Then, $\frac{b-EX}{b-a}e^{\lambda a}+\frac{EX-a}{b-a}e^{\lambda b}=e^{L(h)}$ since $EX=0$

Taking derivative of $L(h)$, $L(0)=L'(0)=0$ and $L^{''}(h)\leq \frac{1}{4}$ By Tayor's expansion, $$L(h)\leq \frac{1}{8}h^2=\frac{1}{8}\lambda^2(b-a)^2$$ Hence,$\mathbf{E}\left[e^{\lambda X}\right] \leq e^{\frac{1}{8}\lambda^2(b-a)^2}$

I was wondering whether the proof has actually used Jensen's inequality? I don't think so.

Thanks!

-
It does so in the first line, doesn't it? – Hagen von Eitzen Oct 16 '12 at 8:40

Since $e^{\lambda x}$ is a convex function, we have $$e^{\lambda x}\leq \frac{b-x}{b-a}e^{\lambda a}+\frac{x-a}{b-a}e^{\lambda b} \qquad \forall a\leq x\leq b.$$
Thanks! But it is derived based on $e^{\lambda x}\leq \frac{b-x}{b-a}e^{\lambda a}+\frac{x-a}{b-a}e^{\lambda b} \forall a\leq x\leq b$, and then apply expectation on both sides. Is it really Jensen's inequality? – Tim Oct 16 '12 at 8:49
My apologies; I was a tad confused as well. The usual Jensen's inequality for convex functions was used (some use this inequality to define a convex function, in particular if it isn't twice differentiable). In this particular case, there is no need to invoke the other (probabilistic) Jensen: $\mathbf E \phi(X) \le \phi(\mathbf EX)$. – Lord_Farin Oct 16 '12 at 8:59