Jump to content

User:InfoTheorist/Hoeffding's inequality proof

From Wikipedia, the free encyclopedia

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

References

[edit]
  1. ^ Robert Nowak. "Lecture 7: Chernoff's Bound and Hoeffding's Inequality" (PDF). ECE 901 (Summer '09) : Statistical Learning Theory Lecture Notes. University of Wisconsin-Madison. Retrieved May 16, 2014.

P^rh^m (talk) 19:48, 16 May 2014 (UTC)