Hoeffding s inequality

Hoeffding's inequality in probability theory gives an upper bound on the probability for the sum of random variables to deviate from its expectation value.

Suppose

X₁, ..., X_n

are independent random variables. Furthermore assume that the X_i are bounded, i.e.

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

Then for

S_n := X₁+...+X_n

we have the inequality

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

The name is for W. Hoeffding, who published the result in 1963.

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information.