Inequality proof without Stirling's formula involving Binary Entropy

Question

How can I prove this without using Stirling's formula?

$${n\choose an} \le 2^{nH(a)}$$ $$H(a) := -a\log_2a -(1-a)\log_2(1-a)$$

Answer 1

Let $X = \text{Bin}(n, \frac{1}{2})$ be a binomial random variable with $p = \frac{1}{2}$. The Chernoff bound applied to $X$ gives that for $a \ge \frac{1}{2}$ we have

$$\mathbb{P}(X \ge an) \le 2^{-n KL(a, \frac{1}{2})}$$

where

$$\begin{align*} -KL \left( a, \frac{1}{2} \right) &= - a \log_2 \frac{a}{\frac{1}{2}} - (1 - a) \log_2 \frac{1-a}{\frac{1}{2}} \\ &= H(a) + \log_2 \frac{1}{2} = H(a) - 1 \end{align*}$$

which gives

$$\mathbb{P}(X \ge an) \le 2^{n H(a) - n}$$

and similarly if $a \le \frac{1}{2}$ we get

$$\mathbb{P}(X \le an) \le 2^{n H(1-a) - n} = 2^{n H(a) - n}.$$

Since $\mathbb{P}(X \ge an)$ is $2^{-n}$ times a sum of binomial coefficients starting at ${n \choose an}$, and similary for $\mathbb{P}(X \le an)$, we get a bound slightly stronger than the desired bound by multiplying by $2^n$, although only for values of $a$ such that $an$ is an integer.