for , Markov's inequality and the independence of implies: This upper bound is the best for the value of minimizing the value inside the exponential. This can be done easily by optimizing a quadratic, giving Writing the above bound for this value of , we get the desired bound: Usage Confidence intervals Hoeffding's inequality can be used to derive confidence intervals. We consider a coin that shows heads with probability and tails with probability . We toss the coin times, generating samples (which are i.i.d Bernoulli random variables). The expected number of times the coin comes up heads is . Furthermore, the probability that the coin comes up heads at least 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 : Since this bound holds on both sides of the mean, Hoeffding's inequality implies that the number of heads that we see is concentrated around its mean, with exponentially small tail. Thinking of as the "observed" mean, this probability can be interpreted as the level of significance (probability of making an error) for a confidence interval around of size 2: Solving the above for gives us the following: Therefore, we require at least samples to acquire a -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 there are more efficient methods of estimating a confidence interval. See also Concentration inequality – a summary of tail-bounds on random variables. Hoeffding's lemma Bernstein inequalities (probability theory) Notes References . Probabilistic inequalities