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
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
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 , then
Furthermore, 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. and
for some measurable function and some constant . Then