A lovely counting inequality

25 Aug, 2025

I stumbled upon this very nice inequality bounding the number of Boolean vectors of length $n$ which have no more than $\rho n$ nonzero entries. (This has some applications to data availability sampling, and, in particular to ZODA, which I might write about soon.)

Let $n$ be any number and set $0<\rho \le 1/2$. Assume, for simplicity, that $\rho n$ is an integer (though the general case is obvious with some floors). Then, the following is true:

where $h_2$ is the binary entropy function, defined

An alternative form is

where $h$ is the natural entropy function (i.e., $h_2$ except replacing the ${\log }_2$ with the natural log.)

The only proof I knew of this was via an argument using the moment generating function and a Chernoff bound. On the other hand, I was reading chapter 12 of Cover's information theory and discovered a more elementary proof, which can be seen as a relatively straightforward extension/strengthening of Cover's version in the book.

Proof

Note that (via Binomial expansion)

Certainly, clipping the tail of the right hand side to $\rho n$ means that

Now, note that, since $\rho \le 1/2$ we have that ${\rho }^{\rho n}(1-\rho {)}^{(1-\rho )n}\le {\rho }^i(1-\rho {)}^{n-i}$ for all $i\le \rho n$ since $\rho \le 1-\rho$. From here, the punchline is obvious, but worth writing anyways:

Moving the constant ${\rho }^{\rho n}(1-\rho {)}^{(1-\rho )n}$ to the right hand side gives the result that

as required.