In this section, we give a proof of Hoeffding's inequality[1].
For the proof, we require the following lemma. Suppose is a real random variable with mean zero such that . Then
To prove this lemma, note that if one of or is zero, then and the inequality follows. If both are nonzero, then must be negative and must be positive.
Next, recall that is a convex function on the real line. Thus for any ,
Combining the previous inequality with the fact that results in
where . Next let and define as
Note that is well defined on as and for all ,
since . The definition of implies . By Taylor's theorem, for every real there exists a between and such that
Note that ,
and
where the last inequality holds because for all , . Therefore, . This implies
Using this lemma, we can prove Hoeffding's inequality. Suppose are independent random variables such that for every , , we have . Let . Then for , Markov's inequality and the independence of the 's imply
To get the best possible upper bound, we find the minimum of the right hand side of the last inequality as a function of . Define as
Note that is a quadratic function and thus achieves its minimum at
Thus we get
P^rh^m (talk) 19:48, 16 May 2014 (UTC)