Hoeffding's inequality

In probability theory, Hoeffding's inequality provides an upper bound on the probability that the sum of independent random variables deviates from its expected value. Hoeffding's inequality was proved by Wassily Hoeffding in 1963.

Hoeffding's inequality is a special case of the Azuma–Hoeffding inequality, and it is more general than the Bernstein inequality, proved by Sergei Bernstein in 1923. They are also special cases of McDiarmid's inequality.

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 p and tails with probability 1 − p. We toss the coin n times. The expected number of times the coin comes up heads is pn. Furthermore, the probability that the coin comes up heads at most k times can be exactly quantified by the following expression:

where H(n) is the number of heads in n coin tosses.

When k = (p − ε)n for some ε > 0, Hoeffding's inequality bounds this probability by a term that is exponentially small in ε²n:

...
Wikipedia