Lesson 10

Proof. [Proof of Chernoff's theorem] For \(\varepsilon=1\), the required upper bound is trivial. Suppose now that \(\varepsilon>1\). \[\begin{align*}\Pr[\alpha \ge \varepsilon\operatorname{E}[\alpha]]&=\Pr\left[\varepsilon^{\alpha} \ge \varepsilon^{\varepsilon\operatorname{E}[\alpha]}\right] \le&\text{(Markov's inequality)}\\&\le \frac{\operatorname{E}[\varepsilon^\alpha]}{\varepsilon^{\varepsilon\operatorname{E}[\alpha]}}\le&\text{(auxiliary lemma)}\\&\le \frac{e^{(\varepsilon-1)\operatorname{E}[\alpha]}}{\varepsilon^{\varepsilon\operatorname{E}[\alpha]}}=\\&=e^{-(\varepsilon\ln\varepsilon-\varepsilon+1)E[\alpha]} .\end{align*}\]◼