I would like to evaluate the asymptotic value of the following sum:
$$f(N)=\frac{1}{2^N}\sum_{n=0}^{N} \binom{N}{n} \log_{2} \binom{N}{n}$$
This is related to the computation of the Shannon entropy. Any help would be greatly appreciated!
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityI would like to evaluate the asymptotic value of the following sum:
$$f(N)=\frac{1}{2^N}\sum_{n=0}^{N} \binom{N}{n} \log_{2} \binom{N}{n}$$
This is related to the computation of the Shannon entropy. Any help would be greatly appreciated!
Laplace's Method: For large $N$ the summand as function of $n$ is maximal at $n=\frac{N}{2}$. This can be seen by the Laplace-deMoivre approximation of the binomial $$ {N \choose n}\sim 2^{N}\sqrt{\frac{2}{\pi N}} \exp\left (-\frac{2}{N}\left(n-\frac{N}{2}\right)^2\right ) $$ Thus replace $n=\frac{N}{2}+\tau$. And indeed, when expanding the natural logarithm of the summand in $\tau$ up to second order in $\tau$, one gets an expression with a constant term and a (negative) term proportional to $\tau^2$, no linear term. It gets quite bulky (to bulky for me to type), but your favourite algebraic calculation tool does that for you.
What is left, is integrating the exponential of the last expression (remember we expanded the natural logarithm of the summand) from $\tau=-\infty$ to $+\infty$. The integral converges (the factor at $\tau^2$ is negative). Then expand the result of the integration for large $N$. Again the algebraic tool will help. The result is $$ N-\frac{\log_2 N}{2}+\frac{1}{2}-\frac{1 + \ln \pi}{2 \ln 2}+O(N^{-1}) $$
I did the calculations with Mathematica. If desired, I would be happy to give more detailed description later.
What you have is related to the entropy $\mathbb{H}(N,p)$ of a Binomial with uniform distribution $p=1/2,$ which is $$ \sum_{n=0}^{N}\frac{\binom{N}{n}}{2^N} \log_2 \left(\frac{\binom{N}{n}}{2^N}\right). $$ There is some recent work by Cheragchi which has looked at this, see the arXiv paper here. For a general $p\in[0,1],$ he derives the expressions $$ \mathbb{H}(N,p)=N h_2(p)+\int_0^\infty\left(\frac{(1-p+pe^{-t})^N+(p+(1-p)e^{-t})^N-e^{-Nt}-1}{t(e^t-1)}\right)\,dt, $$ and $$ \mathbb{H}(N,p)=N h_2(p)+\sum_{j=2}^{\infty} \binom{N}{j}(-1)^jc(j)(p^j+(1-p)^j-1), $$ where $h(\cdot)$ is the binary entropy function, and $$ c(j)=-\sum_{k=0}^{j-1}(-1)^k \binom{j-1}{k}\log(k+1). $$
Math experiment done with Mathematica
ClearAll[k, n]; Table[N[Sum[Binomial[k, n]*Log[2, Binomial[k, n]], {n, 0, k}]/(2^k*k),
12], {k, 100, 3000, 100}]
{0.956309885908,0.975654896780,0.982794988048,0.986577442688,0.988940025511,0.990564159008,0.991753284436,0.992663720635,0.993384459964,0.993970012393,0.994455691464,0.994865412628,0.995215966563,0.995519499229,0.995785020717,0.996019360229,0.996227791142,0.996414452142,0.996582638209,0.996735006151,0.996873722684,0.997000572971,0.997117041463,0.997224372954,0.997323619298,0.997415675569,0.997501308365,0.997581178169,0.997655857185,0.997725843678}
suggests the sum under consideration is equivalent to $2^N N$ as $N\to\infty$.