Chernoff Bounds

Last updated Dec 4, 2021 Edit Source

• All
• Math statistics

Tags: #Math/Statistics

probabilitycourse.com - Chernoff Bounds

zotero:@ChernoffBounds(zotero://select/items/@ChernoffBounds)

• The generic Chernoff bound for a random variable $X$ is attained by applying Markov’s inequality to $e^{tX}$. This gives a bound in terms of the moment-generating function of $X$. For every $t ≥ 0$:

$$\operatorname{Pr}(X \geq a)=\operatorname{Pr}\left(e^{t \cdot X} \geq e^{t \cdot a}\right) \leq \frac{E\left[e^{t \cdot X}\right]}{e^{t \cdot a}}$$

• $E\left[e^{t \cdot X}\right]$实际上就是moment-generating function: $M_{X}(s)$

$$\begin{array}{ll} P(X \geq a) \leq e^{-t a} M_{X}(t), & \text { for all } t>0 \\ P(X \leq a) \leq e^{-t a} M_{X}(t), & \text { for all } t<0 \end{array}$$