Lesson 9

To prove Chernoff's theorem, we start by proving an auxiliary lemma. Already from its formulation, one notices that one of the ideas of the proof is to consider the random variable \(\varepsilon^{\alpha}\).

Lemma. Let \(\alpha_{1},\dotsc,\alpha_{n}\) be independent random variables taking values in \([0,1]\), let \(\alpha=\alpha_{1}+\dotsb+\alpha_{n}\), and let \(\varepsilon\ge1\). Then \[\operatorname{E}[\varepsilon^{\alpha}] \le e^{(\varepsilon-1)\operatorname{E}[\alpha]} ,\] Proof. It is known that the function \(\varepsilon^{x}\) is convex for \(\varepsilon \ge 1\), therefore for all \(0 \le x \le 1\) the inequality \(\varepsilon^{x} \le 1+(\varepsilon-1)x\) holds.

First, we prove that the required inequality holds for \(\alpha_{i}\). In the formula below, summation is carried out over all values of the random variable \(\alpha_{i}\). We will significantly use the fact that all of them lie in the interval \([0,1]\).

\[\begin{align*}\operatorname{E}[\varepsilon^{\alpha_i}]&=\sum_{a}\varepsilon^{a}\Pr[\alpha_{i}=a] \le&\text{(convexity)}\\&\le \sum_{a}(1+(\varepsilon-1)a)\Pr[\alpha_{i}=a] =\\&=\sum_{a}\Pr[\alpha_{i}=a]+(\varepsilon-1)\sum_{a}a\Pr[\alpha_{i}=a]=\\&=1+(\varepsilon-1)\operatorname{E}[\alpha_{i}]\le&\text{(\(1+x \le e^{x}\))}\\&\le e^{(\varepsilon-1)E[\alpha_i]} .\end{align*}\]

Now we prove it for \(\alpha=\alpha_{1}+\dotsb+\alpha_{n}\). In the inequality below, we will use the statement of the lemma just proven for all \(\alpha_{i}\), as well as the fact that any functions of independent random variables are also independent.

\[\begin{align*}\operatorname{E}[\varepsilon^{\alpha}]&=\operatorname{E}\left[\varepsilon^{\alpha_1+\dotsb+\alpha_n}\right]=\\&=\operatorname{E}\left[\varepsilon^{\alpha_1}\dotsb\varepsilon^{\alpha_n}\right]\le&\text{(independence)}\\&= e^{(\varepsilon-1)\operatorname{E}[\alpha_1]}\dotsb e^{(\varepsilon-1)\operatorname{E}[\alpha_n]}=\\&= e^{(\varepsilon-1)(\operatorname{E}[\alpha_1]+\dotsb +\operatorname{E}[\alpha_n])}=\\&=e^{(\varepsilon-1)E[\alpha]} .\end{align*}\]◼