A Chernoff bound for sums of independent Bernoulli trials

Fix $\lambda >0$ and apply [L1] to the nonnegative variable $e^{-\lambda S}$. Because $e^{-\lambda t}$ decreases with $t$, we get $\mathbb{P}(S\le (1-\alpha )\mu )\le e^{\lambda (1-\alpha )\mu }\mathbb{E}[e^{-\lambda S}]$.

Since $S={\sum }_i{X}_i$, we have $e^{-\lambda S}={\prod }_i{e}^{-\lambda X_i}$. The family $(e^{-\lambda X_i}{)}_i$ is still independent, so [L3] and [L2] give $\mathbb{E}[e^{-\lambda S}]={\prod }_{i=1}^k\mathbb{E}[e^{-\lambda X_i}]=((1-p)+p{e}^{-\lambda }{)}^k\le \exp (-\mu (1-e^{-\lambda }))$, using $1-u\le e^{-u}$ with $u=p(1-e^{-\lambda })$.

Combine steps 1.1 and 1.2, and choose $\lambda$ so that $e^{-\lambda }=1-\alpha$. Then $\mathbb{P}(S\le (1-\alpha )\mu )\le \exp (\mu (-(\alpha )+(1-\alpha )\log \frac{1}{1-\alpha }))$.

Define $g(\alpha ):=-(\alpha )+(1-\alpha )\log \frac{1}{1-\alpha }+{\alpha }^2\mathrm{/}2$. Then $g(0)=0$ and $g^{\mathrm{\prime }}(\alpha )=\alpha +\log (1-\alpha )\le 0$ because $\log (1-\alpha )\le -\alpha$ for $0<\alpha <1$. Hence $g(\alpha )\le 0$, which is exactly $-(\alpha )+(1-\alpha )\log \frac{1}{1-\alpha }\le -{\alpha }^2\mathrm{/}2$. Substituting this into step 2.1 gives the claimed bound.