Hoeffding's inequality

Hoeffding's inequality, named after Wassily Hoeffding, is a result in probability theory that gives an upper bound on the probability for the sum of random variables to deviate from its expected value.

Suppose

X₁, ..., X_n

are independent random variables with finite first and second moments. Furthermore assume that the X_i are bounded, i.e.

<math>\Pr(X_i \in [a_i, b_i]) = 1<math>.

Then for

S_n = X₁ + ... + X_n

we have the inequality

<math>\Pr(S_n – \mathbb{E} S_n \geq t) \leq \exp \left( – \frac{2\,t^2}{\sum_{i=1}^n (b_i – a_i)^2} \right).\,<math>

Related inequalities are Markov's inequality and Chernoff's inequality.

Sources

• Wassily Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (301): 13–30, March 1963.