Hoeffding's inequality

Statement

Let $X_1, \dots, X_n$ be independent real random variables with $a_i \le X_i \le b_i$ almost surely, where $a_i < b_i$ are reals. Let $S_n = X_1 + \dots + X_n$ . Then for each $t > 0$ , $P\left(S_n - E[S_n] \ge t\right) \le \exp\left(-\frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2}\right).$

Remarks

The same bound holds for $P(S_n - E[S_n] \le -t)$ . So $P(|S_n - E[S_n]| \ge t) \le 2 \exp\left(-2t^2 / \sum_i (b_i - a_i)^2\right)$ . The proof uses the Chernoff bound together with Hoeffding's lemma: $E[e^{s(X - E[X])}] \le e^{s^2 (b - a)^2 / 8}$ if $a \le X \le b$ . For $n$ independent tosses of a coin with $P(\text{heads}) = p$ , the fraction $H$ of heads satisfies $P(|H - p| \ge \varepsilon) \le 2 e^{-2n\varepsilon^2}$ .

History

The inequality is named after Wassily Hoeffding.

Tag	`0WPDNXGSSN`
URI	`m2://0WPDNXGSSN`
Kind	statement, theorem
Writing	W0 stub
MSC	60E15
Status	This copy of the site has no build data. Run `m2 status 0WPDNXGSSN`.
Uses	Independence of random variables, Expected value, Chernoff bound
Same as	Wikidata Q1622794 Wikipedia Hoeffding's inequality

Tag

0WPDNXGSSN

URI

m2://0WPDNXGSSN

Kind

statement, theorem

Writing

W0 stub

MSC

60E15

Status

This copy of the site has no build data. Run m2 status 0WPDNXGSSN.

Uses

Independence of random variables, Expected value, Chernoff bound

Same as

Wikidata Q1622794

Wikipedia Hoeffding's inequality

Hoeffding's inequality

Statement

Remarks

History

Reading path

Where this leads

Further reading

What this page needs for W1

What links here

Used by