Hoeffding's inequality can be applied to the important special case of identically distributed Bernoulli random variables, and this is how the inequality is often used in combinatorics and computer science. We consider a coin that shows heads with probability and tails with probability. We toss the coin times. The expected number of times the coin comes up heads is. Furthermore, the probability that the coin comes up heads at most times can be exactly quantified by the following expression: where is the number of heads in coin tosses. When for some, Hoeffding's inequality bounds this probability by a term that is exponentially small in : Similarly, when for some, Hoeffding's inequality bounds the probability that we see at least more tosses that show heads than we would expect: Hence Hoeffding's inequality implies that the number of heads that we see is concentrated around its mean, with exponentially small tail. For example, taking gives:
General case of bounded random variables
Let be independent random variables bounded by the interval : . We define the empirical mean of these variables by One of the inequalities in Theorem 1 of states where. Theorem 2 of is a generalization of the above inequality when it is known that are strictly bounded by the intervals : which are valid for positive values of. Here is the expected value of. The inequalities can be also stated in terms of the sum of the random variables: Note that the inequalities also hold when the have been obtained using sampling without replacement; in this case the random variables are not independent anymore. A proof of this statement can be found in Hoeffding's paper. For slightly better bounds in the case of sampling without replacement, see for instance the paper by.
General case of sub-Gaussian random variables
A random variable is called sub-Gaussian, if for some c>0. For a random variable, the following norm is finite if and only if it is sub-Gaussian: Then let be zero-mean independent sub-Gaussian random variables, the general version of the Hoeffding's inequality states that: where c > 0 is an absolute constant. See Theorem 2.6.2 of for details.
Proof
In this section, we give a proof of Hoeffding's inequality. The proof uses Hoeffding's Lemma: Using this lemma, we can prove Hoeffding's inequality. Suppose are independent random variables such that Let Then for, Markov's inequality and the independence of implies: 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 Note that is a quadratic function and achieves its minimum at Thus we get
Usage
Confidence intervals
Hoeffding's inequality is useful to analyse the number of required samples needed to obtain a confidence interval by solving the inequality in Theorem 1: The inequality states that the probability that the estimated and true values differ by more than is bounded by e−2nt2. Symmetrically, the inequality is also valid for another side of the difference: By adding them both up, we can obtain two-sided variant of this inequality: This probability can be interpreted as the level of significance for a confidence interval around of size 2: Solving the above for gives us the following: Therefore, we require at least samples to acquire -confidence interval. Hence, the cost of acquiring the confidence interval is sublinear in terms of confidence level and quadratic in terms of precision. Note that this inequality is the most conservative of the three in Theorem 1, and there are more efficient methods of estimating a confidence interval.
