Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
It does so in the first line, doesn't it? –  Hagen von Eitzen Oct 16 '12 at 8:40
add comment

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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
    
@Tim : The inequality you mentionned is based on the convexity of the exponential function. This is nothing else than a Jensen's inequality. –  Ahriman Oct 16 '12 at 8:53
    
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
    
Can you point out which version of Jensen's inequality is used in the proof? I am confused. –  Tim Oct 16 '12 at 9:12
    
@Ahriman: "This is nothing else than a Jensen's inequality." Do you mean it uses some version of Jensen's inequality? –  Tim Oct 16 '12 at 9:12
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.