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 at height $0.72$ with two peaks close to $0$ and $1$ of height $0.84$.

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!

## Attempt 1

For large $n$, the dominating terms in the summation in $I_n$ come from values $k \approx np$. Expanding $h(\frac{k}{n})$ around $k = np$ leads to $$h\left(\frac{k}{n}\right) = h(p) + \left(\frac{k}{n} - p\right) h'(p) + \frac{1}{2}\left(\frac{k}{n} - p\right)^2 h''(p) + \frac{1}{6}\left(\frac{k}{n} - p\right)^3 h^{(3)}(p) + \dots.$$ Substituting this back into the definition of $I_n(p)$, this leads to $$I = \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \left[-\left(\tfrac{k}{n} - p\right) h'(p) - \tfrac{1}{2}\left(\tfrac{k}{n} - p\right)^2 h''(p) - \tfrac{1}{6}\left(\tfrac{k}{n} - p\right)^3 h^{(3)}(p) - \dots\right].$$ Now the term $\frac{k}{n}$ leads to a factor $\frac{np}{n} = p$ when pulled out of the summation, so the first term disappears. As the second term is simply the variance (scaled by a factor $1/n^2$), this term results in $\frac{1}{2n} p(1-p)h''(p)$. As $h'(p) = \log_2(\frac{1-p}{p})$ and $h''(p) = -1/[p(1-p)\ln 2]$, the second term contributes $1/(2n \ln 2) \approx \frac{0.72}{n}$ as expected. So we have: $$I_n(p) = \frac{1}{2n \ln 2} + \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \left[- \tfrac{1}{6}\left(\tfrac{k}{n} - p\right)^3 h^{(3)}(p) - \dots\right].$$ At this point, what remains is to show that all remaining order terms are small, if $np(1-p) = \omega(1)$.

## Attempt 2

Using the approach described here, consider the sum $$S = \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \frac{k}{n} \log_2 \frac{k}{n}.$$ First, we can cancel the $\frac{k}{n}$ with factors in the binomial coefficient, and pull out a factor $p$ to obtain $$S = p \sum_{k=1}^n \binom{n-1}{k-1} p^{k-1} (1-p)^{n-k} \log_2 \frac{k}{n} = p \sum_{k=0}^{n-1} \binom{n-1}{k} p^{k} (1-p)^{n-k-1} \log_2 \frac{k+1}{n}.$$ Applying Jensen's inequality, we obtain $$S \leq p \log_2\left(\sum_{k=0}^{n-1} \binom{n-1}{k} p^{k} (1-p)^{n-k-1} \frac{k+1}{n}\right) = p \log_2 \frac{(n-1)p + 1}{n}.$$ Pulling out the term $\log_2 p$, we obtain $$S \leq p \log_2 p + p \log_2\left(1 + \frac{1 - p}{np}\right).$$ Applying the same procedure to the other term in $I_n(p)$, this leads to $$I_n(p) \leq h(p) + \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \left[\frac{k}{n} \log_2 \frac{k}{n} + \frac{n-k}{n} \log_2 \frac{n-k}{n}\right] \\ = h(p) + \left[p \log_2 p + p \log_2\left(1 + \frac{1 - p}{np}\right)\right] + \left[(1-p) \log_2 (1-p) + (1-p) \log_2\left(1 + \frac{p}{n(1-p)}\right)\right] \\ = p \log_2\left(1 + \frac{1 - p}{np}\right) + (1-p) \log_2\left(1 + \frac{p}{n(1-p)}\right)$$ Using $\ln(1 + x) \leq x$ for all $x$, this leads to $$I_n(p) \leq \frac{1 - p + p}{n \ln 2}.$$ Unfortunately this is a factor $2$ off, as $I_n(p) \sim \frac{1}{2n \ln 2}$ for almost all $p$.

6more comments