TOPICS
Search

Hoeffding Inequality

The Hoeffding inequality bounds the probability that a sum of bounded independent random variables differs from its expectation value. Let X_1,...,X_n be independent random variables satisfying a_i<=X_i<=b_i almost surely, where a_i and b_i are finite real numbers, and let S_n=X_1+...+X_n. Here and below, E[X] denotes the expectation value of a random variable X. Assume sum_(i=1)^(n)(b_i-a_i)^2>0. Then, for t>0,

P(S_n-E[S_n]>=t)<=exp(-(2t^2)/(sum_(i=1)^(n)(b_i-a_i)^2)).

Applying the same bound to both tails gives

P(|S_n-E[S_n]|>=t)<=2exp(-(2t^2)/(sum_(i=1)^(n)(b_i-a_i)^2)).

If all a_i=b_i, then S_n=E[S_n] almost surely and both tail probabilities are zero for t>0.

See also

Chernoff Bound, Expectation Value, Random Variable, Tail Probability

Explore with Wolfram|Alpha

References

Hoeffding, W. "Probability Inequalities for Sums of Bounded Random Variables." J. Amer. Statist. Assoc. 58, 13-30, 1963. https://doi.org/10.1080/01621459.1963.10500830.

Cite this as:

Weisstein, Eric W. "Hoeffding Inequality." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HoeffdingInequality.html

Subject classifications