Chernoff bound

Statement

Let $X$ be a real random variable with moment-generating function $M_X(t) = E[e^{tX}]$ , and let $a \in \mathbb{R}$ . Then $P(X \ge a) \le \inf_{t > 0} e^{-ta} M_X(t).$

Remarks

Proof: for each $t > 0$ , $\{X \ge a\} = \{e^{tX} \ge e^{ta}\}$ . Markov's inequality gives $P(X \ge a) \le e^{-ta} E[e^{tX}]$ . Then take the infimum over $t$ . For a sum $S$ of independent $X_i$ , $M_S = \prod_i M_{X_i}$ . So the bound becomes $\inf_{t > 0} e^{-ta} \prod_i M_{X_i}(t)$ , which decreases exponentially in many cases. For $S \sim \operatorname{Bin}(n, p)$ with mean $\mu = np$ and $0 < \delta$ , a standard consequence is $P(S \ge (1 + \delta)\mu) \le \left(e^{\delta} / (1 + \delta)^{1 + \delta}\right)^{\mu}$ .

History

The bound is named after Herman Chernoff.

Tag	`014PEBGDYF`
URI	`m2://014PEBGDYF`
Kind	statement, theorem
Writing	W0 stub
MSC	60E15
Status	This copy of the site has no build data. Run `m2 status 014PEBGDYF`.
Uses	Markov's inequality, Moment-generating function
Same as	Wikidata Q1070305 Wikipedia Chernoff bound

Tag

014PEBGDYF

URI

m2://014PEBGDYF

Kind

statement, theorem

Writing

W0 stub

MSC

60E15

Status

This copy of the site has no build data. Run m2 status 014PEBGDYF.

Uses

Markov's inequality, Moment-generating function

Same as

Wikidata Q1070305

Wikipedia Chernoff bound

Chernoff bound

Statement

Remarks

History

Reading path

Where this leads

Further reading

What this page needs for W1

What links here

Used by