Lesson 8

Now, let's present the general formulation of the inequality.

Theorem (Chernoff, 1952). Let \(\alpha=\alpha_{1}+\dotsb+\alpha_{n}\) be the sum of mutually independent random variables \(\alpha_{1}, \dotsc, \alpha_{n}\), each taking values in the interval \([0,1]\). Then for any \(\varepsilon \ge 1\) \[\Pr[\alpha \ge \varepsilon \operatorname{E}[\alpha]] \le e^{-t(\varepsilon)\operatorname{E}[\alpha]}\ ,\] where \(t(\varepsilon)=\varepsilon\ln \varepsilon - \varepsilon + 1\).