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 with probability 1, and let S_n=X_1+...+X_n. Here and below, E[X] denotes the expectation value of a random variable X. 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)).

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