Reference for entropy of the binomial distribution?

Question

The Wikipedia page Binomial distribution says that the entropy of the Binomial(n,p) is $\frac{1}{2}\log_2\left(2\pi e n p (1-p)\right) + O\left(\frac{1}{n}\right)$.

What is a reference (paper or textbook) for this fact? In particular I care about the $O\left(\frac{1}{n}\right)$. It would be ideal to find a source that gives the constant in this expression.

After much searching online, the closest I could find is this pdf of "Entropy Computations Via Analytic Depoissonization", Jacquet and Szpankowski 1997, which gives a full expansion of the error term but no hint as to how one might actually bound this error term. Also, I don't know if that would be the right paper to cite even if I deduce such a bound from their paper myself.

Answer 1

I found one approach, although we get a $1/(np)$ term rather than $1/n$.

According to [1], for any integer-valued random variable $X$ (including a Binomial) with variance $V$, we have \begin{align} H(X) &\leq \frac{1}{2} \log_2 \left[ 2\pi e \left(V + \frac{1}{12}\right) \right] . \end{align} This is already very nice/useful, and probably often quite tight for a Binomial except maybe cases where $np = O(1)$ as $n \to \infty$. (The intuition is that Gaussian distributions maximize entropy for a fixed variance, and the Binomial approaches the Gaussian.) But we can also rearrange: \begin{align} H(X) &\leq \frac{1}{2} \log_2 \left[ 2\pi e V \left(1 + \frac{1}{12V}\right) \right] \\ &= \frac{1}{2} \log_2 \left[ 2 \pi e V \right] + \frac{1}{2} \log_2 \left[ 1 + \frac{1}{12V} \right] \\ &\leq \frac{1}{2} \log_2 \left[ 2\pi e V \right] + \frac{1}{24V\ln(2)} \end{align} using that $\ln(1+x) \leq x$, so $\log_2(1+x) = \ln(1+x)/\ln(2) \leq x/\ln(2)$.

In particular for Binomial$(n,p)$, the variance is $np(1-p)$ so this gives $$ H(X) \leq \frac{1}{2} \log_2\left[2\pi e np (1-p) \right] + \frac{1}{24\ln(2) np(1-p)}. $$

Edit The paper with the best bounds I could find is [2], but they are somewhat complex. The additive $O(1/\text{variance})$ term seems unlikely to be avoidable.

---

[1] "On the Entropy of Integer-Valued Random Variables". Massey, 1988. http://www.isiweb.ee.ethz.ch/archive/massey_pub/pdf/BI527.pdf

[2] "Sharp Bounds on the Entropy of the Poisson Law and Related Quantities". Adell, Lekuona, Yu. http://arxiv.org/abs/1001.2897

Answer 2

Hint:

I can tell you how it is obtained and you can work out. First you will simply write down the definition of entropy, which is the expected value of the logarithm of $1/P(X)$ where $X$ is your random variable which has a Binomial distribution. Then the one who found that result used Central Limit theorem. Using the CLT approximation of Binomial distribution. The first term in the given result is simply the entropy of Gaussian distribution with variance $np(1-p)$. The other term is the residue due to CLT approximation.