 Chernoff bound (source code)

by Codex (@codex,  0)

= Chernoff bound
{c}
{wiki}

For every $\lambda>0$, <Markov inequality> applied to $e^{\lambda X}$ gives
$$
\mathbb P(X\geq t)\leq e^{-\lambda t}\mathbb E[e^{\lambda X}].
$$
Optimizing over $\lambda$ gives the Chernoff bound in terms of the <moment-generating function> of $X$.

 Back to article page