Proof of (i). Starting from the binomial expansion of \(1 = (p + (1-p))^n\),

Since \(0 \le p \le 1 - 1/q\) implies \(\frac{p}{(q-1)(1-p)} \le 1\), and \(i \le pn\) in the sum, raising a number in \([0,1]\) to a larger power can only decrease it, so \(\left(\frac{p}{(q-1)(1-p)}\right)^i \ge \left(\frac{p}{(q-1)(1-p)}\right)^{pn}\) for every \(i \le pn\). Hence

where the last line uses \(q^{-H_q(p)n} = \left(\frac{p}{q-1}\right)^{pn} (1-p)^{(1-p)n}\), which follows directly from the definition of \(H_q\). Rearranging gives \(\mathrm{Vol}_q(pn,n) \le q^{H_q(p)n}\), which proves (i).

Proof of (ii). By Stirling’s approximation for \(n!\),

where \(\ell (n) = \dfrac {e^{\lambda _1(n) - \lambda _2(pn) - \lambda _2((1-p)n)}}{\sqrt{2\pi p(1-p)n}}\) (with \(\lambda _1, \lambda _2\) the error terms of Stirling’s approximation). Then, keeping only the last term of the sum defining \(\mathrm{Vol}_q(pn,n)\),

where the last inequality follows from the definition of \(H_q(\cdot )\) and the fact that \(\ell (n) = q^{-o(n)}\) for large enough \(n\). This proves (ii) and completes the proof.

First note that, by definition of \(H_q(\rho )\) and \(H(\rho )\) (writing \(\log \) for \(\log _2\)),

(\(\Leftarrow \)) Suppose \(q \ge 2^{1/\varepsilon }\). Then \(\log _q(q-1) \le 1\) and \(H(\rho ) \le 1\) for every \(\rho \), and \(\log _2 q \ge 1/\varepsilon \), so

hence \(1 - H_q(\rho ) \ge 1 - \rho - \varepsilon \) for every \(0 {\lt} \rho \le 1 - 1/q\), as desired.

(\(\Rightarrow \)) Suppose \(q = 2^{o(1/\varepsilon )}\). We first claim that for small enough \(\varepsilon \), if \(q \ge 1/\varepsilon ^2\) then \(\log _q(q-1) \ge 1 - \varepsilon \): indeed,

which is at least \(1-\varepsilon \) once \(q \ge 1/\varepsilon ^2\) (and \(\varepsilon \) small enough). Next, if \(q = 2^{o(1/\varepsilon )}\), then for fixed \(\rho \),

Combining, for \(q = 2^{o(1/\varepsilon )}\) with \(q \ge 1/\varepsilon ^2\),

which implies \(1 - H_q(\rho ) {\lt} 1 - \rho - \varepsilon \), as desired. Finally, for \(q \le 1/\varepsilon ^2\), Lemma 97 (applied with \(q\) and \(q^m = 1/\varepsilon ^2\)) shows \(1-H_q(\rho ) \le 1 - H_{1/\varepsilon ^2}(\rho ) {\lt} 1 - \rho - \varepsilon \), using the case already established for the base \(1/\varepsilon ^2 \ge 2^{1/\varepsilon }\). This completes the proof of the “only if” direction.

Since \(H_q'(x) = 0\) at \(x = 1-1/q\), the intuition is that in the Taylor expansion of \(H_q(1-1/q-\varepsilon )\) around \(\varepsilon = 0\) the linear term vanishes; we make this precise assuming \(\varepsilon {\lt} 1/q\). Writing \(x = 1-1/q-\varepsilon \) (so \(1-x = 1/q+\varepsilon \)), by definition of \(H_q\),

Expanding \(\ln (1+x) = x - x^2/2 + x^3/3 - \cdots \) for each logarithm above and collecting the \(\varepsilon ^3\) and smaller terms into \(o(\varepsilon ^2)\), one obtains after simplification

for \(\varepsilon \) small enough. Taking \(c_q = \frac{q^2}{4\ln q\, (q-1)}\) completes the proof.

By definition,

Since every term on the right is non-negative,

which gives the lower bound (the \(\Omega \) half of the claim). For the upper bound, one has \((1-\varepsilon )\log _q(1/(1-\varepsilon )) \le 2\varepsilon /\ln q\) for small enough \(\varepsilon \), so

Together, the two displayed bounds give \(H_q(\varepsilon ) = \Theta \! \left(\frac{1}{\log q}\cdot \varepsilon \log (1/\varepsilon )\right)\), as claimed.