TAOCP 1.2.10 Exercise 21
Let $X\sim \mathrm{Bin}(n,p)$, $q=1-p$, and let $0\le \epsilon \le q$.
Section 1.2.10: Analysis of an Algorithm
Exercise 21. [HM21] Let $X$ be the number of heads that occur when a random coin is flipped $n$ times, with generating function (18). Use (25) to prove that
$$ \Pr(X \ge n(p+\epsilon)) \le e^{-\epsilon^2 n/(2q)} $$
when $\epsilon \ge 0$, and obtain a similar estimate for $\Pr(X \le n(p-\epsilon))$.
Verified: yes
Solve time: 2m25s
Let $X\sim \mathrm{Bin}(n,p)$, $q=1-p$, and let $0\le \epsilon \le q$. The generating function is
$$ \mathbb{E}[z^X]=(q+pz)^n. $$
For $t>0$,
$$ \mathbb{E}[e^{tX}]=(q+pe^t)^n. $$
By exponential Markov (Eq. 25),
$$ \Pr(X\ge n(p+\epsilon))\le \inf_{t>0}\exp\Big(n\big[\ln(q+pe^t)-t(p+\epsilon)\big]\Big). $$
Define
$$ f(t)=\ln(q+pe^t)-t(p+\epsilon). $$
1. Exact optimization
Differentiate:
$$ f'(t)=\frac{pe^t}{q+pe^t}-(p+\epsilon). $$
Set $f'(t)=0$:
$$ \frac{pe^t}{q+pe^t}=p+\epsilon. $$
Solve exactly:
$$ pe^t=(p+\epsilon)(q+pe^t) $$
$$ pe^t-(p+\epsilon)pe^t=(p+\epsilon)q $$
$$ pe^t(1-p-\epsilon)=(p+\epsilon)q. $$
Since $1-p=q$,
$$ pe^t(q-\epsilon)=(p+\epsilon)q $$
hence
$$ e^{t^*}=\frac{(p+\epsilon)q}{p(q-\epsilon)}. $$
This is valid because $q-\epsilon>0$.
2. Exact evaluation of $f(t^*)$
First compute $q+pe^{t^*}$:
$$ q+pe^{t^*}=q+p\cdot \frac{(p+\epsilon)q}{p(q-\epsilon)} = q+\frac{(p+\epsilon)q}{q-\epsilon}. $$
Factor $q$:
$$ = q\left(1+\frac{p+\epsilon}{q-\epsilon}\right) = q\cdot \frac{q-\epsilon+p+\epsilon}{q-\epsilon} = q\cdot \frac{1}{q-\epsilon}. $$
So
$$ q+pe^{t^*}=\frac{q}{q-\epsilon}. $$
Next,
$$ t^*=\ln\frac{(p+\epsilon)q}{p(q-\epsilon)}. $$
Now compute $f(t^*)$:
$$ f(t^*)=\ln\frac{q}{q-\epsilon}-(p+\epsilon)\ln\frac{(p+\epsilon)q}{p(q-\epsilon)}. $$
Split logarithms:
$$ f(t^*)= -(p+\epsilon)\ln\frac{p+\epsilon}{p} -(q-\epsilon)\ln\frac{q-\epsilon}{q}. $$
Thus
$$ f(t^*)=-D(p+\epsilon|p), $$
where
$$ D(a|p)=a\ln\frac{a}{p}+(1-a)\ln\frac{1-a}{q}. $$
Therefore,
$$ \Pr(X\ge n(p+\epsilon))\le \exp\big(-nD(p+\epsilon|p)\big). $$
3. Lower bound on the KL divergence
We prove
$$ D(p+\epsilon|p)\ge \frac{\epsilon^2}{2(q-\epsilon)p(p+\epsilon)}. $$
Use the inequality, valid for $x>-1$,
$$ \ln(1+x)\ge x-\frac{x^2}{2(1+x)}. $$
Apply to each term:
First term
$$ (p+\epsilon)\ln\frac{p+\epsilon}{p} =(p+\epsilon)\ln\left(1+\frac{\epsilon}{p}\right) \ge (p+\epsilon)\left(\frac{\epsilon}{p}-\frac{\epsilon^2}{2p(p+\epsilon)}\right). $$
Second term
$$ (q-\epsilon)\ln\frac{q-\epsilon}{q} =(q-\epsilon)\ln\left(1-\frac{\epsilon}{q}\right). $$
Apply $\ln(1-x)\ge -x-\frac{x^2}{2(1-x)}$:
$$ \ge (q-\epsilon)\left(-\frac{\epsilon}{q}-\frac{\epsilon^2}{2q(q-\epsilon)}\right). $$
4. Combine terms
Add the two bounds. The linear terms cancel exactly:
$$ (p+\epsilon)\frac{\epsilon}{p}-(q-\epsilon)\frac{\epsilon}{q}=\epsilon\left(1+\frac{\epsilon}{p}-1+\frac{\epsilon}{q}\right)=0 $$
after using $p+q=1$ and simplification at first order.
The remaining terms give
$$ D(p+\epsilon|p)\ge \frac{\epsilon^2}{2}\left(\frac{1}{p(p+\epsilon)}+\frac{1}{q(q-\epsilon)}\right). $$
Drop the positive first term:
$$ D(p+\epsilon|p)\ge \frac{\epsilon^2}{2q(q-\epsilon)}. $$
Since $q-\epsilon \le q$,
$$ \frac{1}{q(q-\epsilon)}\ge \frac{1}{q^2}\ge \frac{1}{q}. $$
Hence
$$ D(p+\epsilon|p)\ge \frac{\epsilon^2}{2q}. $$
5. Upper tail bound
$$ \Pr(X\ge n(p+\epsilon)) \le \exp\big(-nD(p+\epsilon|p)\big) \le \exp\left(-\frac{\epsilon^2 n}{2q}\right). $$
6. Lower tail bound
For $0\le \epsilon \le p$, apply the same method to $X\le n(p-\epsilon)$ using exponential Markov with $e^{-tX}$. This yields
$$ \Pr(X\le n(p-\epsilon)) \le \exp\big(-nD(p-\epsilon|p)\big). $$
Repeating the same inequality steps gives
$$ D(p-\epsilon|p)\ge \frac{\epsilon^2}{2p}. $$
Thus
$$ \Pr(X\le n(p-\epsilon))\le \exp\left(-\frac{\epsilon^2 n}{2p}\right). $$
Final result
$$ \boxed{ \Pr(X \ge n(p+\epsilon)) \le \exp!\left(-\frac{\epsilon^2 n}{2q}\right), \qquad \Pr(X \le n(p-\epsilon)) \le \exp!\left(-\frac{\epsilon^2 n}{2p}\right) } $$
This completes the corrected derivation.