1
$\begingroup$

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!

  • 1
    It does so in the first line, doesn't it?2012-10-16

2 Answers 2

1

Jensen's inequality is used in the line:

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.$

  • 0
    @Ahriman: Thanks! Can you be explicit? What are the two elements in the probability space, so that LHS and RHS can be seen as those in a more usual Jensen's inequality?2012-10-17