Theorem for additive form (absolute error) of Chernoff bound from Wikipedia, which I take for granted:
Assume random variables $X_1, X_2, \ldots, X_m$ are i.i.d. Let $p = E \left [X_i \right ], X_i \in \{0,1\}$, and $\varepsilon > 0$. Then $$ \begin{align} &\Pr\left[ \frac 1 m \sum X_i \geq p + \varepsilon \right] \\ &\qquad\leq \left ( {\left (\frac{p}{p + \varepsilon}\right )}^{p+\varepsilon} {\left (\frac{1 - p}{1 -p - \varepsilon}\right )}^{1 - p- \varepsilon}\right ) ^m = e^{ - D(p+\varepsilon\|p) m} \end{align} $$ and $$ \begin{align} &\Pr\left[ \frac 1 m \sum X_i \leq p - \varepsilon \right] \\ &\qquad\leq \left ( {\left (\frac{p}{p - \varepsilon}\right )}^{p-\varepsilon} {\left (\frac{1 - p}{1 -p + \varepsilon}\right )}^{1 - p+ \varepsilon}\right ) ^m = e^{ - D(p-\varepsilon\|p) m}, \end{align} $$ where $$ D(x||y) = x \log \frac{x}{y} + (1-x) \log \frac{1-x}{1-y} $$ is the Kullback-Leibler divergence between Bernoulli distributed random variables with parameters $x$ and $y$ respectively.
I was wondering how the next statement is derived:
If $p\geq 1/2 $, then $\Pr\left[ X>mp+x \right] \leq \exp(-x^2/2mp(1-p)) $.
I thought it might be derived from the first formula, $$\Pr\left[ X>mp+x \right] = \Pr\left[ X/m >p+x/m \right] \leq e^{ - D(p+x/m\|p) m} $$ where $$ D(p+x/m\|p) = (p+x) \ln \frac{p+x}{p} + (1-p-x) \ln \frac{1-p-x}{1-p} $$ but I couldn't reach $\exp(-x^2/2mp(1-p))$ from here.
Thanks!
