Chernoff Inequality

The inequality is also known as Chernoff bound.

Theorem

• $X$,
  • $\mathbb{R}$-valued r.v.
• $a > 0$,
• $t > 0$,

\[\begin{eqnarray} P(X \ge a) & \le & \frac{ \mathrm{E} \left[ e^{t X} \right] }{ e^{ta} } \nonumber \end{eqnarray}\]

proof

$\Box$

Reference

• Chernoff bound - Wikipedia
• chernoff-notes.pdf
• Probability - The Chernoff Bound