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!
$\begingroup$
$\endgroup$
2
-
$\begingroup$ If you want very rough asymptotic, the entropy of the binomial(N,1/2) distribution (to which your question is very closely related) should be close to (1/2)log N on the basis that the binomial distribution is something like a uniform distribution over $\sqrt N$ bins. $\endgroup$– Anthony QuasCommented Apr 12, 2019 at 6:08
-
$\begingroup$ @AnthonyQuas it is indeed very close to $(1/2)\log(N \pi e /2)$, see math.stackexchange.com/questions/244455/… $\endgroup$– usulCommented Apr 12, 2019 at 11:12
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
1
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). $$
-
1$\begingroup$ For a closed-form but presumably rougher bound, the entropy of the Bionmial(0.5,N) distribution is $0.5\log(0.5 N \pi e) + O(1/N)$. E.g. math.stackexchange.com/questions/244455/… $\endgroup$– usulCommented Apr 12, 2019 at 11:11
$\begingroup$
$\endgroup$
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$.
