math lessons - 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.

$\Pr(X_i \in [a_i, b_i]) = 1$ .

Then for

S_n = X₁ + ... + X_n

we have the inequality

$\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).\,$

Sources

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