Skip to main content
4 of 8
added 193 characters in body
TMM
  • 733
  • 10
  • 25

Expected centered entropy of the binomial distribution

In short, the function I am interested in is the following: $$I_n(p) = \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \left[h(p) - h\left(\tfrac{k}{n}\right)\right],$$ where $h(x) \triangleq -x \log x - (1-x) \log (1-x)$ is the standard binary entropy function. I am able to prove that for large $n$ this function attains a local maximum around $p \approx \frac{1.338}{n}$ at which $I_n(p) \approx \frac{0.84}{n}$ in case binary logarithms are used. By assuming that $p = \frac{\alpha}{n}$ for $\alpha = O(1)$ and using a Poisson approximation of the binomial distribution, the value $\alpha \approx 1.338$ is a (numerically found) maximizing value of $$\max_{\alpha > 0} \left\{\sum_{z=1}^{\infty} \frac{\alpha^z}{z!} e^{-\alpha} (z \log z) - \alpha \log \alpha\right\}.$$ Note that the latter expression does not contain $n$ anymore; I am interested in large-$n$ asymptotics of $I_n(p)$ which leads to the above, $n$-independent expression.

What I would like to show is that this point $p = \frac{\alpha}{n}$ is actually not just a local, but a global maximum, i.e., there are no values $p = \omega(\frac{1}{n})$ with even higher asymptotic values of $I_n(p)$ for large $n$. So my question can be formulated as:

Can we prove that for large $n$, $\max\limits_{p \in [0,1]} I_n(p) \to I_n(\frac{\alpha}{n})$ with $\alpha \approx 1.338184$?

Numerical inspection of $I_n(p)$ for say $n = 100\,000$ shows that $I_n(p) \propto \frac{1}{n}$ is nice and smooth, has two global maxima at $\frac{\alpha}{n}$ and $1 - \frac{\alpha}{n}$ with value $\frac{0.84}{n}$ and a local minimum at $p = \frac{1}{2}$ with value $\frac{0.72}{n}$ (and two trivial minima at $0$ and $1$ with value $0$). The figure below sketches what $I_n(p)$ (scaled with a factor $n$) looks like for small $n$. As $n$ increases, the function might be best described as a flat line on $(0,1)$ with two peaks close to $0$ and $1$.

enter image description here

I've tried various approaches using e.g. Taylor expansions of the entropy, but I am not able to prove that "order terms" are actually small for arbitrary $p$. Also, a bound given here using Jensen's inequality is not sharp enough; it's roughly a factor $2$ too loose to prove the above statement.

Any help would be appreciated!

TMM
  • 733
  • 10
  • 25