Exercise 5.3: Packing of the Boolean Hypercube
Consider a $\delta$-packing. Then the $\tfrac12 \delta$-balls do not intersect. Hence, the total number of elements in the union of those balls is at most $2^d$. Set $\tilde\delta = 2\lfloor\tfrac12 \delta d\rfloor/d \le \delta$. Then \begin{equation} M(\delta) \sum_{i=1}^{\tilde\delta d/2} \binom{d}{i} \le 2^d \iff \log M(\delta) \le - \log \sum_{i=1}^{\tilde\delta d/2} \binom{d}{i} 2^{-d} = - \log \P(Z_d \le \tfrac12 \tilde\delta d) \end{equation} where $Z_d$ is the sum of $d$ $\Ber(\tfrac12)$ variables. Therefore, by the lower bound from Exercise 2.10, \begin{equation} \frac1d \log M(\delta) \le \KL( \tfrac12 \tilde\delta, \tfrac12 ) + \frac1d \log(d + 1). \end{equation} The above derivation is valid but upper bounds by $\tilde\delta$ rather than by $\delta$! It is possible to upper bound $\KL(\tfrac12 \tilde\delta, \tfrac12)$ by some multiple of $\KL(\tfrac12 \delta, \tfrac12)$ using that $\tilde \delta$ and $\delta$ are close, but this would yield a worse bound than required.