Exercise 2.10: Lower Bounds on Binomial Tails
(a)
Use \(\P ( Z_n \leq \delta n ) \geq \P ( Z_n = m )\) with \(m = \lfloor \delta n \rfloor\)
\begin{align} \frac{1}{n} \log \sum_{i=0}^m { n \choose i } \alpha^i (1 - \alpha)^{n - i} &\geq \frac{1}{n} \log {n \choose m} \alpha^m (1 - \alpha)^{n - m} \newline &= \frac{1}{n} \log {n \choose m} + \tilde{\delta} \log \alpha + (1 - \tilde{\delta}) \log (1 - \alpha) \, . \end{align}
(b)
Exponentiating and rearranging, all we need to establish is \begin{equation} {n \choose m} \tilde{\delta}^m (1 - \tilde{\delta})^{n - m} \geq \frac{1}{n + 1} \, . \end{equation} If \(m = \argmax_{\ell \in \{0 , \ldots , 1 \}} \P (Y = \ell)\), \(Y \sim \Binom(n , \tilde{\delta})\), then \begin{equation} 1 = \sum_{i = 0}^n \P (Y = i) \leq (n + 1) \P (Y = m) \, , \end{equation} implying the result holds. To see \(m = \argmax_{\ell \in \{0 , \ldots , 1 \}} \P (Y = \ell)\) \begin{align} \frac{\P (Y = m) }{ \P (Y = (m + 1) \wedge n)} &= \frac{(m + 1) \wedge n}{m} &\geq 1 \, , \newline \frac{\P (Y = m) }{ \P (Y = (m - 1) \vee 0)} &= \frac{n - [(m - 1) \vee 0]}{n - m} &\geq 1 \, , \end{align} This argument can be applied inductively in both directions (\(m + k\) and \(m - k\)), yielding the result.
(c)
Combining (a) and (b) \begin{align} (n + 1) \P (Z_n \leq \delta n) &\geq \exp \left\lbrace n \left[ \phi(\tilde{\theta}) + \tilde{\delta} \log (\alpha) + (1 - \tilde{\delta}) \log(1 - \alpha) \right] \right\rbrace \newline &= \exp \left\lbrace - n \, D (\tilde{\delta} \, \| \, \alpha) \right\rbrace \, . \end{align}
Notes
- The first edition of the book had \(D (\delta \, \| \, \alpha )\) in place of \(D (\tilde{\delta} \, \| \, \alpha )\) in (c). This was a typo.