Exercise 2.9: Sharp Upper Bounds on Binomial Tails
(a)
We proceed with the Chernoff method: \begin{equation} \P(Z_n \le \delta n) \le \P(e^{- \lambda Z_n} \ge e^{- \lambda \delta n}) \le e^{\lambda \delta n} \E[e^{- \lambda Z_n}] = e^{\lambda \delta n} (\alpha e^{- \lambda} + (1 - \alpha))^n. \end{equation} Hence, \begin{equation} \log \P(Z_n \le \delta n) \le n(\lambda\delta + \log(\alpha e^{- \lambda} + (1 - \alpha))). \end{equation} If we set the derivative of the r.h.s. with respect to $\lambda$ to zero and solve we find \begin{equation} \lambda = \log \frac{\alpha}{\delta} - \log \frac{1 - \alpha}{1 - \delta} > 0. \end{equation} This indeed gives the desired result: \begin{equation} \log \P(Z_n \le \delta n) \le -n \parens{ \delta \log \frac{\delta}{\alpha} + (1 - \delta) \log \frac{1 - \delta}{1 - \alpha} } = -n \KL(\delta, \alpha). \end{equation}
(b)
Using that \(Z_n \in \SG(\tfrac12 \sqrt{n})\), we find that \begin{equation} \P(Z_n \le \delta n) = \P(-(Z_n - \alpha n) \le (\alpha - \delta) n) \le \exp\parens{ -2(\delta - \alpha)^2 n }, \end{equation} so \begin{equation} \log \P(Z_n \le \delta n) \le -n \cdot 2(\delta - \alpha)^2. \end{equation} Then verify that \begin{equation} \KL(\delta, \alpha) \ge 2 (\delta - \alpha)^2. \end{equation}