Chernoff-Hoeffding I'm looking for a proof for a particular application of Chernoff's inequality in the case of the binomial distribution:
https://en.wikipedia.org/wiki/Chernoff_bound#Additive_form_(absolute_error)
in this wikipedia article there are some preliminary steps in the previous section:
https://en.wikipedia.org/wiki/Chernoff_bound#Example
but I can't seem to be able to complete the proof myself (have been working on in for a while now and getting rather frustrated... any help will be most appreciated... I believe I may be just getting lost in the algebra or something...)
I was told there's a complete proof in the appendix of 'the probabilistic method', but I cant' find it there. 
in the 'example' in the wikipedia article, they are using a taylor expansion of e^x... are they applying the same inequality also in the binomial case?
I've seen other questions here in this website about this topic but couldn't find a refence to a complete proof anywhere... thought it was implied they're not too hard to find. 
 A: Chernoff bound for Binomial random variable
Let $X_{i}\stackrel{iid}\sim\text{Ber}(p)$, $i\in[n]$ and let $X=\frac{1}{n}\sum_{i=1}^{n}X_{i}$. We have, for any $t>0$ and $\lambda>0$,
\begin{align*}
\mathbb{P}(X-p\ge t)&\le \frac{\mathbb{E}e^{\lambda(X-p)}}{e^{\lambda t}}\\
&=e^{-\lambda (p+t)}(\mathbb{E}e^{\frac{\lambda X_{1}}{n}})^{n}.~~~~~~\quad(1)
\end{align*}
Now,
\begin{equation}
\mathbb{E}e^{\frac{\lambda X_{1}}{n}}=pe^{\frac{\lambda}{n}}+1-p.
\end{equation}
Substituting this in $(1)$,
\begin{align}
\mathbb{P}(X-p\ge t)&\le\exp(-n\{\frac{\lambda}{n}(p+t)-\log(pe^{\frac{\lambda}{n}}+1-p)\}).~~~~~~\quad(2)
\end{align}
This bound can now be optimized over $\lambda>0$. You can check that the optimal value $\lambda^{*}$ is
\begin{equation}
\frac{\lambda^{*}}{n}=\log\bigg(\frac{(1-p)(p+t)}{p(1-p-t)}\bigg).
\end{equation}
Finally, substituting this into $(2)$ and simplifying a bit, we get
\begin{equation}
\mathbb{P}(X-p\ge t)\le D(\text{Ber}(p+t)\|\text{Ber}(p)).
\end{equation}
Hope this answers your question.
