Understanding measure concentration inequalities

Question

In the spirit of this question Understanding proof of a lemma used in Hoeffding inequality , I am trying to understand the steps that lead to Hoeffding's inequality.

What holds the most mystery for me in the proof is the part where exponential moments are computed for the sum of i.i.d variables, after-which Markov's inequality is applied.

My goal is to understand: Why does this technique give a tight inequality, and is it the tightest we can achieve? A typical explanation refers to the moment generating properties of the exponent. Yet, I find this too vague.

A post in Tao's blog, http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/#hoeff, might hold some answers.

With this goal in mind, my question is about three points in Tao's post which I am stuck at and which I hope could give insight once explained.

1. Tao derives the following inequality using the k-th moment$$\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq 2 (\frac{\sqrt{ek/2}}{\lambda})^k. \ \ \ \ \ (7)$$ If this is true for any k, he concludes an exponential bound. This is where I'm lost. $$\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq C \exp( - c \lambda^2 ) \ \ \ \ \ (8)$$

2. Hoeffding's lemma is presented: Lemma 1 (Hoeffding’s lemma) Let ${X}$ be a scalar variable taking values in an interval ${[a,b]}$. Then for any ${t>0}$, $$\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} (1 + O( t^2 {\bf Var}(X) \exp( O( t (b-a) ) ) ). \ \ \ \ \ (9)$$ In particular $$\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} \exp( O( t^2 (b-a)^2 ) ). \ \ \ \ \ (10)$$ The proof of Lemma 1 begins by taking expectation over the taylor expansion $\displaystyle e^{tX} = 1 + tX + O( t^2 X^2 \exp( O(t) ) )$ .Why can the expansion be bounded by that quadratic term? and how does equation 10 follow?

3. Finally, an exercise is given:
   Exercise 1 Show that the ${O(t^2(b-a)^2)}$ factor in (10) can be replaced with ${t^2 (b-a)^2/8}$, and that this is sharp. This would provide a much shorter proof than the one in Understanding proof of a lemma used in Hoeffding inequality , but I do not know how to solve this.

Any further intuitions\explanations about the proof of the inequality or the reason we cannot derive a tighter bound are definitely welcome.

Answer 1

The use of exponential moments is a common step in the process of proving concentration of measure inequalities. My understanding is as follows 1) By using $\mathbb{E}e^X$ rather than $\mathbb{E} X$, one captures all the moments of $X$, rather than just the first moment. Hence, it is always advantageous to bound $\mathbb{E} e^X$, rather than bound $\mathbb{E}X$, as there is more information in $\mathbb{E} e^X$. Why does $\mathbb{E} e^X$ have more information? An informal explanation is given by the fact that a Taylor expansion of $e^{X}=1+X+\frac{X^2}{2}+\frac{X^3}{6}+\ldots$. As you can see all the powers of $X$ are involved. Hence, when you take $\mathbb{E}X$, you essentially end up bounding all moments of $X$.