# Proof of Hoeffding's inequality

The Hoeffding's inequality is $P(S_n - E[S_n] \geq \epsilon) \leq e^{-2\epsilon^2/k'}$, where $S_n = \sum_{i=1}^{n} X_i$, $X_i$'s are independent bounded random variables, and $k'$ depends on the random variables. In the proof of Hoeffding's inequality, an optimization problem of the form is solved: $$\min_{s} \ \ e^{-s\epsilon}e^{ks^2}$$ subject to $s > 0$, to obtain a tight upper bound (which in turn yields the Hoeffding's inequality). It turns out that $s = \epsilon/2k$ is the value that obtains the Hoeffding's inequality. I don't see how.

EDIT: Note that $k > 0, \epsilon > 0$.

-
I see that the problem is convex. I hope I'm have not misinterpreted the way $s$ is found to tighten the bound. –  Naga Nov 1 '10 at 4:07
Could you write up the proof or include a link to it somewhere? It would then be helpful if you could point exactly to the place in the proof where you are having trouble. –  Mike Spivey Nov 1 '10 at 5:12
Since $f(s)=e^{ks^2-s\epsilon}$ has derivative $f'(s)=(2ks-\epsilon) e^{ks^2-s\epsilon}$, which is negative for $s<\epsilon/2k$ and positive for $s>\epsilon/2k$, the minumum is attained at $s=\epsilon/2k$. Is that what's causing you trouble, or is it something else later on that you haven't told us about? –  Hans Lundmark Nov 1 '10 at 7:09
Yes, I was making a silly mistake. I think that's it. However, even for the function to be convex, we need something $s >= \epsilon/2k$ I guess. –  Naga Nov 1 '10 at 13:11

Since $\exp$ is monotone increasing, your problem is equivalent to minimizing the quadratic $ks^2 - \epsilon s = k(s - \epsilon/2k)^2 - \epsilon^2/4k$.