In this post, we prove a concentration inequality for bounded independent random variables due to Hoeffding.

Lemma 1.Suppose is a real-valued random variable with and almost surely, for some positive constant . Then

*Proof. *We first show that, for fixed,

Note that the function is convex on , since

Since , we have by convexity that

Denote the distribution function of by . Then since , we have the inequality

Applying the Taylor expansion to the preceding expression, we see that

which completes the proof.

Note that if , almost surely, where are finite constants, then the preceding argument gives us the upper bound

We can use Hoeffding’s inequality to obtain a special case of the Azuma-Hoeffding concentration inequality. Let be independent random variables where almost surely lies in the compact interval for . Then by Markov’s inequality and independence,

for all . Applying Hoeffding’s inequality to the random variables to obtain

Set and consider the function . Since the upper is an upper bound for the LHS above for all , we now to turn to finding the minimizing value . Completing the square, we can write

Hence,

Applying the same argument to , we also have the upper bound

Combining these two results, we obtain the following tail bound for :

We summarize these results with the following theorem.

Theorem 2.(Hoeffding)Suppose are independent random variables, where , almost surely. If , then

and

We now use Hoeffding’s inequality to obtain a concentration inequality, apparently known as Khintchine’s inequality or proved in some form by Khintchine, for finite sums with random signs.

Theorem 3(Khintchine’s Inequality).Suppose are i.i.d. random variables with , and are arbitrary real numbers. If and , thenFurthermore, for , there exist finite constants independent of such that

*Proof.** *To obtain the tail bound, we apply Hoeffding’s inequality with to obtain

We now turn to proving the second assertion. Using the “layer-cake” representation of the expected value, we have

We make the change of variable to obtain

Taking the root of both sides completes the proof of the upper bound. For the lower bound, first note by Hölder’s inequality, , where . Since the are independent, we have that and therefore

Taking completes the proof.

I leave it as an exercise to the reader to the prove the following generalization of Hoeffding’s inequality:

Theorem 4.Let be random variables such that a.e. andfor some measurable function and some constant . Then

Pingback: Azuma-Hoeffding Inequality | Math by Matt