<p>(Edited from previous version, 2014-04-08.)</p>

<p>I believe that the answer is $\epsilon_n \to \log(\sqrt{e}) \approx 0.7213475...$ where the logarithm is base 2. This seems to match simulation results. I don't have a full formal proof, but give the heuristic approximations/calculations.</p>

<p>I think it's easier to note that your question is equivalent to:</p>

<blockquote>
  <p>What are the asymptotics of $\delta_n = 1 - \mathbb{E}[H(k/n)]$, where the expectation is over $k \sim Binomial(n,0.5)$?</p>
</blockquote>

<p>(where $H$ is the binary entropy function $H(p) = p\log(1/p) + (1-p)\log(1/(1-p))$, and $\delta_n = \epsilon_n/n$.)</p>

<p>Here's a quick plot to show the idea. We have the binary entropy function in blue and the Binomial pmf (for $p=0.5$) in green. So we can see that the expectation of $H(k/n)$, when $k$ is distributed binomially, will always be below one but should be approaching one. The question is how fast.</p>

<p><img src="https://i.sstatic.net/LhwTW.png" alt="Binary entropy function and Binomial(n,0.5) pmf, where n=100"></p>

<p>The key idea will be that the value we're interested in,
  $$ \mathbb{E}[H(k/n)] = \sum_{k=0}^n \frac{{n \choose k}}{2^n} H\left(\frac{k}{n}\right) , $$
can be related entropy of the binomial distribution. Let $p_{n,k} = \frac{{n \choose k}}{2^n}$ be the probability of $k$ heads in $n$ fair coin flips. The steps will be as follows:</p>

<ol>
<li>Use Stirling's approximation to get $H(k/n) = \frac{\log(p_{n,k})}{n} + 1 + \text{something}$.</li>
<li>Rewrite the original sum to get $\mathbb{E}[H(k/n)] = 1 - \frac{H(Binom(n,0.5))}{n} + \sum \text{something}$.</li>
<li>Get that the entropy of the binomial, divided by $n$, plus the sum of "something", equals $\frac{\log(\sqrt{e})}{n} + O(1/n^2)$.</li>
</ol>

<p><strong>Step 1:</strong></p>

<p>Just plugging in Stirling and doing some cancellation/rearranging,
\begin{align}
   p_{n,k} &amp;:= \frac{{n \choose k}}{2^n} \\
    &amp;\sim \frac{n^n}{k^k (n-k)^{n-k}}\frac{1}{2^n}\sqrt{\frac{n}{2\pi k (n-k)}} .
\end{align}</p>

<p>This won't be very tight for every term in the sum, but I think it will be asmyptotically tight towards the middle, which is all that matters since all the probability is in the center.</p>

<p>We can rewrite the entropy function as follows. It's just some arithmetic to combine the logarithms.
\begin{align}
 H(k/n) &amp;= \frac{k}{n}\log\left(\frac{1}{k/n}\right) + \frac{n-k}{n}\log\left(\frac{1}{(n-k)/n}\right) \\
  &amp;= \log\left(\frac{n}{k^{k/n}(n-k)^{(n-k)/n}}\right) .
\end{align}</p>

<p>So, using Sterling's approximation above, the logarithm of a probability term is
\begin{align}
 \log(p_{n,k}) &amp;= \log\left(\frac{{n \choose k}}{2^n}\right) \\
  &amp;\approx n H(k/n) - n + \log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) .
\end{align}</p>

<p><strong>Step 2:</strong>
\begin{align}
 \mathbb{E}[H(k/n)] &amp;= \sum_{k=0}^n p_{n,k} H(k/n)  \\
  &amp;\approx \sum_{k=0}^n p_{n,k} \left(\frac{\log(p_{n,k})}{n} + 1 - \frac{\log\left(\sqrt{\frac{n}{2\pi k (n-k)}}\right)}{n}\right) \\
  &amp;= 1 - \frac{H(Binom(n,0.5))}{n} - \frac{1}{n}\sum_{k=0}^n p_{n,k}\log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) .
\end{align}
Here, $H(Binom(n,0.5))$ is the entropy of the Binomial distribution for $n$ coin flips and $p=0.5$, which by wikipedia is $\log\left(\sqrt{\pi e n / 2}\right) + O(1/n)$.</p>

<p><strong>Step 3:</strong></p>

<p>Now, we just need to approximate the third sum. I will take a very rough approximation (feel free to do better, but it probably doesn't gain much). All the probability mass is concentrated on $k = \frac{n}{2} \pm o(n)$. So approximate this sum (which is an expectation) by its value on the term $k=\frac{n}{2}$, when it is $\log\left(\sqrt{\frac{2}{\pi n}}\right)$.</p>

<p>So now, we get
\begin{align}
 \delta_n &amp;\approx \frac{\log\left(\sqrt{\pi e n/2}\right)}{n} + \frac{\log\left(\sqrt{2/\pi n}\right)}{n} \pm O\left(\frac{1}{n^2}\right) \\
          &amp;= \frac{\log\left(\sqrt{e}\right)}{n} \pm O\left(\frac{1}{n^2}\right) .
\end{align}</p>

CC BY-SA 3.0
2014-04-08T21:35:34.307Z
Thank you very much for your effort. Your attempt is useful and i like your ideas, but i am not quite sure about the details. I will think about it and maybe i will ask some questions soon..
Danny
CC BY-SA 3.0
2014-04-09T01:24:21.413Z
@Danny, sure thing. Let me know if parts are unclear. The computation is not fully rigorous, particularly (1) the use of Stirling's approximation everywhere (a fix might be to only consider an interval where the Binomial probability is $\Omega(1/n)$ and argue that Stirling is asymptotically tight there) and (2) the approximation of the "third term" by just setting $k=n/2$ (a fix might be to again consider the high-probability interval and see if the error is small).
usul
CC BY-SA 3.0
2014-04-09T13:35:09.260Z
My first question is a general question: You think that $\mathbb{E}_{w \in \{0,1\}^n} nH(w) = n-\mathcal{O}(1)$. Do you think there is a "short" proof for this conjecture without getting the exact term $\varepsilon_{n}$ respectively the exact limit of $\varepsilon_{n}$, which you are considering to be $\log\sqrt{e}$?
Danny
CC BY-SA 3.0
2014-04-09T20:51:01.670Z
@Danny, I'm not sure how to get this with a shorter proof, but maybe another answer will do so.
usul
CC BY-SA 3.0
2014-04-10T09:07:06.387Z
Thanks again for your help. Everything seems to be clear..
Danny
CC BY-SA 3.0
2014-04-08T16:08:47.497Z
2014-04-09T03:18:58.643Z
2014-04-09T03:18:58.643Z
usul
<p>Here is a proof that the quantity # that OP considers tends to n(1-o(1)).</p>

<blockquote>
  <p>Claim: #=n-o(n)</p>
</blockquote>

<p>First, note that for any function $f:\{0, 1\}^n \rightarrow \mathbb{R}$, $\frac{1}{2^n} \sum_{w \in \{0,1\}^n} f(w)$ is exactly the same as $\mathbb{E}_{w \in \{0,1\}^n} f(w)$. So you're asking whether $\mathbb{E}_{w \in \{0,1\}^n} H(w) = 1-o(1)$.</p>

<p>To see this, define $X$ to be a random variable uniformly distributed on $\{0,1\}^n$ Let $X_0$ be the number of 0's in $X$ and $X_1$ be the number of 1's in $X$. We want to prove 
$$
\mathbb{E}[(X_0/n)\log(n/X_0)+(X_1/n)\log(n/X_1)]=1-o(1). 
$$
But we know from the law of large numbers that both $X_0/n$ and $X_1/n$ converge in probability to $1/2$ and that if a random variable $Y$ converges in probability to $c$ and if $f$ is a continuous function, then $f(Y)$ converges in probability to $f(c)$. So we get that $\mathbb{E}[(X_0/n)\log(n/X_0)+(X_1/n)\log(n/X_1)]$ converges in probability to $\frac12 \log(2) + \frac12 \log(2) = 1$, QED.</p>

<p>Note: This claim is related to the Asymptotic equipartition property for discrete-time i.i.d. sources <a href="http://en.wikipedia.org/wiki/Asymptotic_equipartition_property#AEP_for_discrete-time_i.i.d._sources" rel="nofollow">here</a>.</p>

CC BY-SA 3.0
2014-04-08T15:06:40.113Z
I'm sorry, but I can't see how $\mathbb{E}_{w\in\left\{0,1\right\}^{n}}\left[H\left(\frac{|w|_{0}}{n},\frac{|w|_{1}}{n}\right)\right]=1-o(1)$ is a direct result of the AEP, since we are looking for the expectation of entropies for all empirical distributions and the AEP treats with the limit of the selfinformations of strings for some fixed distribution. Can you specify that implication?
Danny
CC BY-SA 3.0
2014-04-08T15:18:22.780Z
Also I do not see why your statement $\mathbb{E}[(X_0/n)\log(n/X_0)+(X_1/n)\log(n/X_1)]=1-o(1)$ leads directly to my conjecture..  
Thanks for your help.
Danny
CC BY-SA 3.0
2014-04-09T01:26:01.677Z
*So you're asking whether* $\mathbb{E}_{w\in\{0,1\}^n}H(w) = 1 - o(1)$. Note this isn't quite so, the question as worded is whether it is $1 - o(1/n)$.
usul
CC BY-SA 3.0
2014-04-09T11:39:01.317Z
@Danny, the expression $\mathbb{E}[(X_0/n)\log (n/X_0) + (X_1/n) \log (n/X_1)]$ is exactly the same as your expression $H_0(w)$ (or, in my notation, $H_0(X)$).
greg
CC BY-SA 3.0
2014-04-09T11:44:10.203Z
@Danny You're right, the theorem does not follow from the AEP as easily as I thought. Rather than explain how it follows, I'll just leave my self-contained explanation, which turns out to be simpler than relating to the AEP.
greg
CC BY-SA 3.0
2014-04-09T11:55:12.697Z
@usul Thanks! I didn't realize that Danny's asking whether it is 1-o(1/n). I now see it, and have updated my answer accordingly.
greg
CC BY-SA 3.0
2014-04-09T13:27:37.147Z
@mobius dumpling Thanks, I see. Your proof of $\mathbb{E}_{w \in \{0,1\}^n} H_{0}(w) = 1-o(1)$ is (like you already said) not exactly what I'm looking for, but nonetheless very helpful! Thanks again!
Danny
CC BY-SA 3.0
2014-04-08T13:22:03.343Z
2014-04-15T15:52:23.417Z
2014-04-15T15:52:23.417Z
greg
<p>I will prove that for all $n$, $H_n = n - \epsilon_n$ where $0 &lt; \epsilon_n &lt; 1$.</p>

<p>Let $f_{\alpha}(t) = 4^{\alpha} t^{\alpha}(1 - t)^{\alpha} $. I will not prove this, but you can find some $\alpha^*$ such that for all $\alpha \ge \alpha^*$, $f_{\alpha}(t) \le H(t)$. Also, for $\delta \ll 1$,  you can find $\alpha'$ such that for all $\alpha \le \alpha'$, $f_{\alpha'}(t) \ge H(t)$ in $[\delta, 1 - \delta]$. I will assume $\alpha =  1$ and $\alpha = 0.5$ lead to the two different types of functions.</p>

<p>My point is that you can use simpler functions to obtain the bound you need. Here I will use $f_{\alpha}(t)$.</p>

<p>Let $H_n$ be the empirical entropy that you are looking for and $F(n, \alpha)$ be the value obtained when I replace $H(\frac{k}{n})$ with $f_{\alpha}(\frac{k}{n})$.
We have</p>

<p>$F(n, \alpha) = n2^n \sum_{k = 0}^{n} {n \choose k} f_{\alpha}(\frac{k}{n})
 = n 2^n 4^{\alpha} \sum_{k = 0}^{n} {n \choose k} \left( \frac{k}{n} \right) ^ {\alpha} \left(1 - \frac{k}{n} \right) ^\alpha = n 4^{\alpha} E\left[\left(  \frac{k}{n} - \frac{k^2}{n^2} \right)^{\alpha} \right] = n2^n 4^{\alpha} \sum_{k = 0}^{n / 2} {n \choose k} \left(\frac{k}{n} \right)^{2 \alpha}$</p>

<p>For $\alpha = 1$, we know $F(n, \alpha) \le H_n$ and direct evaluation says that $F(n, 1) = n - 1$, which is true for all $n$.</p>

<p>For $\alpha = 0.5$, we know $F(n, \alpha) \ge H_n$ and a direct evaluation leads to $F(n, 0.5) = n 4^{0.5} E[\frac{k}{n}] = n$. </p>

<p>Therefore, for all $n &gt; 0$, $n\ge H_n \ge n - 1$.</p>

<p>I found it nontrivial to try this for any $\alpha &lt; 1.0$ other than $\alpha = 0.5$. </p>

CC BY-SA 3.0
2014-04-09T20:47:44.080Z
2014-04-09T20:58:38.310Z
2014-04-09T20:58:38.310Z
Ehsan
<p>Here is another approach, based on information theory and heavily inspired by @usul's answer. It shows that $\epsilon_n=O(1)$ with very few calculations, and can be used to prove that $\epsilon_n \rightarrow \log_2 \sqrt{e}$ and to derive good estimates on the rate of convergence with less calculations than @usul's approach. In fact, I find a closed-form expression for $\epsilon_n$ : $$(1)  \; \; \; \; \epsilon_n = n \left( H(Binom(n,1/2)) - H \left( Binom \left( n-1, 1/2 \right) \right) \right) \ .$$</p>

<p>Details:</p>

<p>Let $X$ be a uniform random variable in $\{0,1\}^n$. Let $K$ be a random variable equal to the number of 1's in $X$. The expression $\#$ that @Danny wants to analyze is exactly equal to $n \cdot \mathbb{E}_{k} [H(X_1 | K=k)]$. (Here $X_1$ is the first bit of $X$.) By the basic properties of the entropy operator,
$$(2)  \; \; \; \; \# = n\mathbb{E}_{k} [H(X_1 | K=k)]=nH(X_1|K)=n(H(X_1K)-H(K))=n(H(K|X_1)+H(X_1)-H(K)) = n(1-H(Binom(n,1/2)) + H(Binom(n-1,1/2))) \ .$$
The last equality follows from the fact that $X_1$ is just a uniformly random bit, $K$ is the binomial distribution, and $K|(X_1=x_1)$ is distributed either as $Binom(n-1,1/2)$ or as $Binom(n-1,1/2)+1$, depending on the value of $x_1$, both of which have the same entropy.</p>

<p>This already gave us equation (1). Now we just need to calculate to get the value of $\lim_{n \rightarrow \infty} \epsilon_n$</p>

<p>We use any known estimation for the entropy of a binomial RV, such as <a href="https://math.stackexchange.com/questions/244455/entropy-of-a-binomial-distribution">here</a>. We see that $$ (3)  \; \; \; \; H(K)=H(Binom(n,1/2))=\frac12 \log_2 ( \pi en / 2) + O(1/n) \ ,$$ and, similarly, that $$H(K|X_1)=H(Binom(n-1,1/2))=\frac12 \log_2 ( \pi e(n-1)/2) + O(1/n) \ .$$ Canceling out terms and substituting into (1), we get $$ (4)  \; \; \; \; \epsilon_n = n \cdot (H(K)-H(K|X_1)) = n \cdot \frac12 (\log_2 (n/(n-1)) + O(1/n)) = \\ \frac12 \log_2 ((n/(n-1))^n) + O(1) \rightarrow \log_2(\sqrt{e}) + O(1) \ . $$</p>

<p>By slightly improving the approximation (3) we should be able to replace the $O(1)$ term in (4) by $O(1/n)$ and therefore get that, indeed, $\lim_{n \rightarrow \infty} \epsilon_n = \log_2 \sqrt{e}$. To get this better estimation it should be enough to check that $H(Binom(n,1/2))=\frac12 \log_2 ( \pi en / 2) + err(n)$ where $err(n)=O(1/n)$ and $err$ is a monotone function.</p>

CC BY-SA 3.0
2014-04-10T10:08:41.270Z
Very nice! I accept usul's answer since your answer is inspired by usul's, but your answer is very elegant (and converts to $\log(\sqrt e)$, too).
Danny
CC BY-SA 3.0
2014-04-10T11:29:54.933Z
*converges instead of "converts" :)
Danny
CC BY-SA 3.0
2014-04-10T13:30:05.173Z
Danny, I'm not sure it's a good idea to accept a more complicated and less elegant answer. Everyone else who ever looks at this question will look at @usul's answer first, while it's in everyone's interest that they look at the most simple and elegant answer first. The solutions to this are: 1. to ask usul to reformulate his answer to be simpler (for all I care, he could copy the text of my answer verbatim if he wants, I don't care about the reputation or anything) or 2. to accept my answer. I'll transfer the relevant reputation to usul if that's possible.
greg
CC BY-SA 3.0
2014-04-15T18:10:28.880Z
This seems like the better answer to accept in my opinion too! Very nice/elegant entropy argument.
usul
CC BY-SA 3.0
2014-04-16T08:02:25.090Z
@mobius dumpling Is there a way to contact you for further interests and researches? If you are interested, there is a link to my page on my profile.
Danny
CC BY-SA 3.0
2014-04-18T18:52:38.050Z
Note that in the literature you'll often see $\log_2\sqrt{e}$ written as $\frac{1}{2\ln 2}$.
Steven Stadnicki
CC BY-SA 3.0
2014-04-18T19:01:46.180Z
@StevenStadnicki Ah, now that term seems familiar! It's some constant appearing in the approximation of the entropy function around p=1/2, IIRC. Or maybe in some inequality between mutual information and statistical distance.
greg
CC BY-SA 3.0
2014-04-09T22:24:04.997Z
2014-04-15T19:50:13.477Z
2017-04-13T12:19:19.363Z
greg
<p>I'm thinking about some properties of the empirical entropy for binary strings of length <span class="math-container">$n$</span> when the following question crosses my way:</p>
<blockquote>
<p><span class="math-container">$\underbrace{\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\left\{0,1\right\}^{n}}\normalsize nH_{0}(w)}_{\large\#}\;\overset{?}{=}\;n-\varepsilon_{n}\;\;\;$</span></p>
<p>with <span class="math-container">$\;\;\lim\limits_{n\rightarrow\infty}\varepsilon_{n}=c\;\;\;$</span> and <span class="math-container">$\;\;\;\forall n:\;\varepsilon_{n}&gt;0$</span></p>
<p>where <span class="math-container">$c$</span> is a constant.</p>
<h3>Is that equation true? For which function <span class="math-container">$\varepsilon_{n}$</span> respectively which constant <span class="math-container">$c$</span>?</h3>
<p><span class="math-container">$ $</span></p>
<p><span class="math-container">$n=2\;\;\;\;\;\;\;\rightarrow\;\#=1 $</span><br />
<span class="math-container">$n=3\;\;\;\;\;\;\;\rightarrow\;\#\approx 2.066 $</span><br />
<span class="math-container">$n=6\;\;\;\;\;\;\;\rightarrow\;\#\approx 5.189 $</span><br />
<span class="math-container">$n=100\;\;\;\rightarrow\;\#\approx 99.275 $</span><br />
<span class="math-container">$n=5000\;\rightarrow\;\#\approx 4999.278580 $</span><br />
<span class="math-container">$n=6000\;\rightarrow\;\#\approx 5999.278592 $</span></p>
</blockquote>
<p><span class="math-container">$ $</span></p>
<h1>Backround</h1>
<p><span class="math-container">$ $</span><br />
<span class="math-container">$H_{0}(w)$</span> is the zeroth-order empircal entropy for strings over <span class="math-container">$\Sigma=\left\{0,1\right\}$</span>:</p>
<ul>
<li><span class="math-container">$H_{0}(w)=\frac{|w|_{0}}{n}\log\frac{n}{|w|_{0}}+\frac{n-|w|_{0}}{n}\log\frac{n}{n-|w|_{0}}$</span></li>
</ul>
<p>where <span class="math-container">$|w|_{0}$</span> is the number of occurences of <span class="math-container">$0$</span> in <span class="math-container">$w\in\Sigma^{n}$</span>.</p>
<p>The term <span class="math-container">$nH_{0}(w)$</span> corresponds to the Shannon-entropy of the empirical distribution of binary words  with respect to the number of occurences of <span class="math-container">$0$</span> respectively <span class="math-container">$1$</span> in <span class="math-container">$w\in\Sigma^{n}$</span>.</p>
<p>More precise:<br />
Let the words in <span class="math-container">$\left\{0,1\right\}^{n}$</span> be possible outcomes of a Bernoulli process. If the probability of <span class="math-container">$0$</span> is equal to the relative frequency of <span class="math-container">$0$</span> in a word <span class="math-container">$w\in\left\{0,1\right\}^{n}$</span>, then the Shannon-entropy of this Bernoulli process is equal to <span class="math-container">$nH_{0}(w)$</span>.</p>
<p>At this point, my question should be more reasonable since the first term normalizes the Shannon-entropies for all empirical distributions of words <span class="math-container">$w\in\left\{0,1\right\}^{n}$</span>.<br />
Intuitively I thought about getting something close to the Shannon-entropy of the uniform distribution of <span class="math-container">$\left\{0,1\right\}^{n}$</span>, which is <span class="math-container">$n$</span>.<br />
By computing and observing some values I've got the conjecture above, but I'm not able to prove it or to get the exact term <span class="math-container">$\varepsilon_{n}$</span>.</p>
<p>It is easy to get the following equalities:</p>
<p><span class="math-container">$\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\left\{0,1\right\}^{n}}\normalsize nH_{0}(w)\;\;=\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\left\{0,1\right\}^{n}}\normalsize |w|_{0}\log\frac{n}{|w|_{0}}+(n-|w|_{0})\log\frac{n}{n-|w|_{0}}$</span></p>
<p><span class="math-container">$=\large\frac{1}{2^{n}}\normalsize\sum\limits_{k=1}^{n-1}$</span> <span class="math-container">$n\choose k$</span> <span class="math-container">$\left(k\log\frac{n}{k}+(n-k)\log\frac{n}{n-k}\right)$</span></p>
<p>and it is possible to apply some logarithmic identities but I'm still in a dead point.</p>
<p>(the words <span class="math-container">$0^{n}$</span> and <span class="math-container">$1^{n}$</span> are ignored, because the Shannon-entropy of their empirical distributions is zero)</p>
<p>Any help is welcome.</p>

CC BY-SA 3.0
2014-04-07T17:36:44.733Z
I don't see a question here.
Suresh Venkat
CC BY-SA 3.0
2014-04-07T17:38:08.190Z
Is the equation above true? Can anybody prove it respectively prove that the equation doesn't hold?
Danny
CC BY-SA 3.0
2014-04-08T15:20:47.700Z
you have a bunch of equations. it would be better to number them. also highlight the question with ">" blockquoting.
vzn
CC BY-SA 3.0
2014-04-09T13:46:09.597Z
I edit my question from $\varepsilon_{n}\rightarrow0$ to  $\varepsilon_{n}\rightarrow c$, where $c$ is a constant.
Danny
<it.information-theory><shannon-entropy>
Expected empirical entropy
Danny
# Expected empirical entropy

(Asked by: username_0 on 2014-04-07)

I'm thinking about some properties of the empirical entropy for binary strings of length $n$ when the following question crosses my way:

> $\underbrace{\large\frac{1}{2^{n}}\normalsize\sum\limits\_{w\in\left\{0,1\right\}^{n}}\normalsize nH\_{0}(w)}\_{\large\#}\;\overset{?}{=}\;n-\varepsilon\_{n}\;\;\;$
>
> with $\;\;\lim\limits\_{n\rightarrow\infty}\varepsilon\_{n}=c\;\;\;$ and $\;\;\;\forall n:\;\varepsilon\_{n}>0$
>
> where $c$ is a constant.
>
> ### Is that equation true? For which function $\varepsilon\_{n}$ respectively which constant $c$?
>
> $ $
>
> $n=2\;\;\;\;\;\;\;\rightarrow\;\#=1 $  
> $n=3\;\;\;\;\;\;\;\rightarrow\;\#\approx 2.066 $  
> $n=6\;\;\;\;\;\;\;\rightarrow\;\#\approx 5.189 $  
> $n=100\;\;\;\rightarrow\;\#\approx 99.275 $  
> $n=5000\;\rightarrow\;\#\approx 4999.278580 $  
> $n=6000\;\rightarrow\;\#\approx 5999.278592 $

$ $

# Backround

$ $  
$H\_{0}(w)$ is the zeroth-order empircal entropy for strings over $\Sigma=\left\{0,1\right\}$:

* $H\_{0}(w)=\frac{|w|\_{0}}{n}\log\frac{n}{|w|\_{0}}+\frac{n-|w|\_{0}}{n}\log\frac{n}{n-|w|\_{0}}$

where $|w|\_{0}$ is the number of occurences of $0$ in $w\in\Sigma^{n}$.

The term $nH\_{0}(w)$ corresponds to the Shannon-entropy of the empirical distribution of binary words with respect to the number of occurences of $0$ respectively $1$ in $w\in\Sigma^{n}$.

More precise:  
Let the words in $\left\{0,1\right\}^{n}$ be possible outcomes of a Bernoulli process. If the probability of $0$ is equal to the relative frequency of $0$ in a word $w\in\left\{0,1\right\}^{n}$, then the Shannon-entropy of this Bernoulli process is equal to $nH\_{0}(w)$.

At this point, my question should be more reasonable since the first term normalizes the Shannon-entropies for all empirical distributions of words $w\in\left\{0,1\right\}^{n}$.  
Intuitively I thought about getting something close to the Shannon-entropy of the uniform distribution of $\left\{0,1\right\}^{n}$, which is $n$.  
By computing and observing some values I've got the conjecture above, but I'm not able to prove it or to get the exact term $\varepsilon\_{n}$.

It is easy to get the following equalities:

$\large\frac{1}{2^{n}}\normalsize\sum\limits\_{w\in\left\{0,1\right\}^{n}}\normalsize nH\_{0}(w)\;\;=\large\frac{1}{2^{n}}\normalsize\sum\limits\_{w\in\left\{0,1\right\}^{n}}\normalsize |w|\_{0}\log\frac{n}{|w|\_{0}}+(n-|w|\_{0})\log\frac{n}{n-|w|\_{0}}$

$=\large\frac{1}{2^{n}}\normalsize\sum\limits\_{k=1}^{n-1}$ $n\choose k$ $\left(k\log\frac{n}{k}+(n-k)\log\frac{n}{n-k}\right)$

and it is possible to apply some logarithmic identities but I'm still in a dead point.

(the words $0^{n}$ and $1^{n}$ are ignored, because the Shannon-entropy of their empirical distributions is zero)

Any help is welcome.

**Tags:** it.information-theory, shannon-entropy

> **Comments:**
> **username_1**: I don't see a question here.  
> **username_0**: Is the equation above true? Can anybody prove it respectively prove that the equation doesn't hold?  
> **username_2**: you have a bunch of equations. it would be better to number them. also highlight the question with ">" blockquoting.  
> **username_0**: I edit my question from $\varepsilon_{n}\rightarrow0$ to  $\varepsilon_{n}\rightarrow c$, where $c$ is a constant.  

---

## 4 answers

### Answer by username_4 on 2014-04-09. Score: 7 | Accepted answer

Here is another approach, based on information theory and heavily inspired by @username_3's answer. It shows that $\epsilon\_n=O(1)$ with very few calculations, and can be used to prove that $\epsilon\_n \rightarrow \log\_2 \sqrt{e}$ and to derive good estimates on the rate of convergence with less calculations than @username_3's approach. In fact, I find a closed-form expression for $\epsilon\_n$ : $$(1) \; \; \; \; \epsilon\_n = n \left( H(Binom(n,1/2)) - H \left( Binom \left( n-1, 1/2 \right) \right) \right) \ .$$

Details:

Let $X$ be a uniform random variable in $\{0,1\}^n$. Let $K$ be a random variable equal to the number of 1's in $X$. The expression $\#$ that @username_0 wants to analyze is exactly equal to $n \cdot \mathbb{E}\_{k} [H(X\_1 | K=k)]$. (Here $X\_1$ is the first bit of $X$.) By the basic properties of the entropy operator,
$$(2) \; \; \; \; \# = n\mathbb{E}\_{k} [H(X\_1 | K=k)]=nH(X\_1|K)=n(H(X\_1K)-H(K))=n(H(K|X\_1)+H(X\_1)-H(K)) = n(1-H(Binom(n,1/2)) + H(Binom(n-1,1/2))) \ .$$
The last equality follows from the fact that $X\_1$ is just a uniformly random bit, $K$ is the binomial distribution, and $K|(X\_1=x\_1)$ is distributed either as $Binom(n-1,1/2)$ or as $Binom(n-1,1/2)+1$, depending on the value of $x\_1$, both of which have the same entropy.

This already gave us equation (1). Now we just need to calculate to get the value of $\lim\_{n \rightarrow \infty} \epsilon\_n$

We use any known estimation for the entropy of a binomial RV, such as [here](https://math.stackexchange.com/questions/244455/entropy-of-a-binomial-distribution). We see that $$ (3) \; \; \; \; H(K)=H(Binom(n,1/2))=\frac12 \log\_2 ( \pi en / 2) + O(1/n) \ ,$$ and, similarly, that $$H(K|X\_1)=H(Binom(n-1,1/2))=\frac12 \log\_2 ( \pi e(n-1)/2) + O(1/n) \ .$$ Canceling out terms and substituting into (1), we get $$ (4) \; \; \; \; \epsilon\_n = n \cdot (H(K)-H(K|X\_1)) = n \cdot \frac12 (\log\_2 (n/(n-1)) + O(1/n)) = \\ \frac12 \log\_2 ((n/(n-1))^n) + O(1) \rightarrow \log\_2(\sqrt{e}) + O(1) \ . $$

By slightly improving the approximation (3) we should be able to replace the $O(1)$ term in (4) by $O(1/n)$ and therefore get that, indeed, $\lim\_{n \rightarrow \infty} \epsilon\_n = \log\_2 \sqrt{e}$. To get this better estimation it should be enough to check that $H(Binom(n,1/2))=\frac12 \log\_2 ( \pi en / 2) + err(n)$ where $err(n)=O(1/n)$ and $err$ is a monotone function.

> **Comments:**
> **username_0**: Very nice! I accept username_3's answer since your answer is inspired by username_3's, but your answer is very elegant (and converts to $\log(\sqrt e)$, too).  
> **username_0**: *converges instead of "converts" :)  
> **username_4**: username_0, I'm not sure it's a good idea to accept a more complicated and less elegant answer. Everyone else who ever looks at this question will look at @username_3's answer first, while it's in everyone's interest that they look at the most simple and elegant answer first. The solutions to this are: 1. to ask username_3 to reformulate his answer to be simpler (for all I care, he could copy the text of my answer verbatim if he wants, I don't care about the reputation or anything) or 2. to accept my answer. I'll transfer the relevant reputation to username_3 if that's possible.  
> **username_3**: This seems like the better answer to accept in my opinion too! Very nice/elegant entropy argument.  
> **username_0**: @mobius dumpling Is there a way to contact you for further interests and researches? If you are interested, there is a link to my page on my profile.  
> **username_6**: Note that in the literature you'll often see $\log_2\sqrt{e}$ written as $\frac{1}{2\ln 2}$.  
> **username_4**: @StevenStadnicki Ah, now that term seems familiar! It's some constant appearing in the approximation of the entropy function around p=1/2, IIRC. Or maybe in some inequality between mutual information and statistical distance.  

---

### Answer by username_3 on 2014-04-08. Score: 4

(Edited from previous version, 2014-04-08.)

I believe that the answer is $\epsilon\_n \to \log(\sqrt{e}) \approx 0.7213475...$ where the logarithm is base 2. This seems to match simulation results. I don't have a full formal proof, but give the heuristic approximations/calculations.

I think it's easier to note that your question is equivalent to:

> What are the asymptotics of $\delta\_n = 1 - \mathbb{E}[H(k/n)]$, where the expectation is over $k \sim Binomial(n,0.5)$?

(where $H$ is the binary entropy function $H(p) = p\log(1/p) + (1-p)\log(1/(1-p))$, and $\delta\_n = \epsilon\_n/n$.)

Here's a quick plot to show the idea. We have the binary entropy function in blue and the Binomial pmf (for $p=0.5$) in green. So we can see that the expectation of $H(k/n)$, when $k$ is distributed binomially, will always be below one but should be approaching one. The question is how fast.

![Binary entropy function and Binomial(n,0.5) pmf, where n=100](https://i.sstatic.net/LhwTW.png)

The key idea will be that the value we're interested in,
$$ \mathbb{E}[H(k/n)] = \sum\_{k=0}^n \frac{{n \choose k}}{2^n} H\left(\frac{k}{n}\right) , $$
can be related entropy of the binomial distribution. Let $p\_{n,k} = \frac{{n \choose k}}{2^n}$ be the probability of $k$ heads in $n$ fair coin flips. The steps will be as follows:

1. Use Stirling's approximation to get $H(k/n) = \frac{\log(p\_{n,k})}{n} + 1 + \text{something}$.
2. Rewrite the original sum to get $\mathbb{E}[H(k/n)] = 1 - \frac{H(Binom(n,0.5))}{n} + \sum \text{something}$.
3. Get that the entropy of the binomial, divided by $n$, plus the sum of "something", equals $\frac{\log(\sqrt{e})}{n} + O(1/n^2)$.

**Step 1:**

Just plugging in Stirling and doing some cancellation/rearranging,
\begin{align}
p\_{n,k} &:= \frac{{n \choose k}}{2^n} \\
&\sim \frac{n^n}{k^k (n-k)^{n-k}}\frac{1}{2^n}\sqrt{\frac{n}{2\pi k (n-k)}} .
\end{align}

This won't be very tight for every term in the sum, but I think it will be asmyptotically tight towards the middle, which is all that matters since all the probability is in the center.

We can rewrite the entropy function as follows. It's just some arithmetic to combine the logarithms.
\begin{align}
H(k/n) &= \frac{k}{n}\log\left(\frac{1}{k/n}\right) + \frac{n-k}{n}\log\left(\frac{1}{(n-k)/n}\right) \\
&= \log\left(\frac{n}{k^{k/n}(n-k)^{(n-k)/n}}\right) .
\end{align}

So, using Sterling's approximation above, the logarithm of a probability term is
\begin{align}
\log(p\_{n,k}) &= \log\left(\frac{{n \choose k}}{2^n}\right) \\
&\approx n H(k/n) - n + \log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) .
\end{align}

**Step 2:**
\begin{align}
\mathbb{E}[H(k/n)] &= \sum\_{k=0}^n p\_{n,k} H(k/n) \\
&\approx \sum\_{k=0}^n p\_{n,k} \left(\frac{\log(p\_{n,k})}{n} + 1 - \frac{\log\left(\sqrt{\frac{n}{2\pi k (n-k)}}\right)}{n}\right) \\
&= 1 - \frac{H(Binom(n,0.5))}{n} - \frac{1}{n}\sum\_{k=0}^n p\_{n,k}\log\left(\sqrt{\frac{n}{2\pi k(n-k)}}\right) .
\end{align}
Here, $H(Binom(n,0.5))$ is the entropy of the Binomial distribution for $n$ coin flips and $p=0.5$, which by wikipedia is $\log\left(\sqrt{\pi e n / 2}\right) + O(1/n)$.

**Step 3:**

Now, we just need to approximate the third sum. I will take a very rough approximation (feel free to do better, but it probably doesn't gain much). All the probability mass is concentrated on $k = \frac{n}{2} \pm o(n)$. So approximate this sum (which is an expectation) by its value on the term $k=\frac{n}{2}$, when it is $\log\left(\sqrt{\frac{2}{\pi n}}\right)$.

So now, we get
\begin{align}
\delta\_n &\approx \frac{\log\left(\sqrt{\pi e n/2}\right)}{n} + \frac{\log\left(\sqrt{2/\pi n}\right)}{n} \pm O\left(\frac{1}{n^2}\right) \\
&= \frac{\log\left(\sqrt{e}\right)}{n} \pm O\left(\frac{1}{n^2}\right) .
\end{align}

> **Comments:**
> **username_0**: Thank you very much for your effort. Your attempt is useful and i like your ideas, but i am not quite sure about the details. I will think about it and maybe i will ask some questions soon..  
> **username_3**: @username_0, sure thing. Let me know if parts are unclear. The computation is not fully rigorous, particularly (1) the use of Stirling's approximation everywhere (a fix might be to only consider an interval where the Binomial probability is $\Omega(1/n)$ and argue that Stirling is asymptotically tight there) and (2) the approximation of the "third term" by just setting $k=n/2$ (a fix might be to again consider the high-probability interval and see if the error is small).  
> **username_0**: My first question is a general question: You think that $\mathbb{E}_{w \in \{0,1\}^n} nH(w) = n-\mathcal{O}(1)$. Do you think there is a "short" proof for this conjecture without getting the exact term $\varepsilon_{n}$ respectively the exact limit of $\varepsilon_{n}$, which you are considering to be $\log\sqrt{e}$?  
> **username_3**: @username_0, I'm not sure how to get this with a shorter proof, but maybe another answer will do so.  
> **username_0**: Thanks again for your help. Everything seems to be clear..  

---

### Answer by username_4 on 2014-04-08. Score: 3

Here is a proof that the quantity # that OP considers tends to n(1-o(1)).

> Claim: #=n-o(n)

First, note that for any function $f:\{0, 1\}^n \rightarrow \mathbb{R}$, $\frac{1}{2^n} \sum\_{w \in \{0,1\}^n} f(w)$ is exactly the same as $\mathbb{E}\_{w \in \{0,1\}^n} f(w)$. So you're asking whether $\mathbb{E}\_{w \in \{0,1\}^n} H(w) = 1-o(1)$.

To see this, define $X$ to be a random variable uniformly distributed on $\{0,1\}^n$ Let $X\_0$ be the number of 0's in $X$ and $X\_1$ be the number of 1's in $X$. We want to prove
$$
\mathbb{E}[(X\_0/n)\log(n/X\_0)+(X\_1/n)\log(n/X\_1)]=1-o(1).
$$
But we know from the law of large numbers that both $X\_0/n$ and $X\_1/n$ converge in probability to $1/2$ and that if a random variable $Y$ converges in probability to $c$ and if $f$ is a continuous function, then $f(Y)$ converges in probability to $f(c)$. So we get that $\mathbb{E}[(X\_0/n)\log(n/X\_0)+(X\_1/n)\log(n/X\_1)]$ converges in probability to $\frac12 \log(2) + \frac12 \log(2) = 1$, QED.

Note: This claim is related to the Asymptotic equipartition property for discrete-time i.i.d. sources [here](http://en.wikipedia.org/wiki/Asymptotic_equipartition_property#AEP_for_discrete-time_i.i.d._sources).

> **Comments:**
> **username_0**: I'm sorry, but I can't see how $\mathbb{E}_{w\in\left\{0,1\right\}^{n}}\left[H\left(\frac{|w|_{0}}{n},\frac{|w|_{1}}{n}\right)\right]=1-o(1)$ is a direct result of the AEP, since we are looking for the expectation of entropies for all empirical distributions and the AEP treats with the limit of the selfinformations of strings for some fixed distribution. Can you specify that implication?  
> **username_0**: Also I do not see why your statement $\mathbb{E}[(X_0/n)\log(n/X_0)+(X_1/n)\log(n/X_1)]=1-o(1)$ leads directly to my conjecture..   Thanks for your help.  
> **username_3**: *So you're asking whether* $\mathbb{E}_{w\in\{0,1\}^n}H(w) = 1 - o(1)$. Note this isn't quite so, the question as worded is whether it is $1 - o(1/n)$.  
> **username_4**: @username_0, the expression $\mathbb{E}[(X_0/n)\log (n/X_0) + (X_1/n) \log (n/X_1)]$ is exactly the same as your expression $H_0(w)$ (or, in my notation, $H_0(X)$).  
> **username_4**: @username_0 You're right, the theorem does not follow from the AEP as easily as I thought. Rather than explain how it follows, I'll just leave my self-contained explanation, which turns out to be simpler than relating to the AEP.  
> **username_4**: @username_3 Thanks! I didn't realize that username_0's asking whether it is 1-o(1/n). I now see it, and have updated my answer accordingly.  
> **username_0**: @mobius dumpling Thanks, I see. Your proof of $\mathbb{E}_{w \in \{0,1\}^n} H_{0}(w) = 1-o(1)$ is (like you already said) not exactly what I'm looking for, but nonetheless very helpful! Thanks again!  

---

### Answer by username_5 on 2014-04-09. Score: 0

I will prove that for all $n$, $H\_n = n - \epsilon\_n$ where $0 < \epsilon\_n < 1$.

Let $f\_{\alpha}(t) = 4^{\alpha} t^{\alpha}(1 - t)^{\alpha} $. I will not prove this, but you can find some $\alpha^\*$ such that for all $\alpha \ge \alpha^\*$, $f\_{\alpha}(t) \le H(t)$. Also, for $\delta \ll 1$, you can find $\alpha'$ such that for all $\alpha \le \alpha'$, $f\_{\alpha'}(t) \ge H(t)$ in $[\delta, 1 - \delta]$. I will assume $\alpha = 1$ and $\alpha = 0.5$ lead to the two different types of functions.

My point is that you can use simpler functions to obtain the bound you need. Here I will use $f\_{\alpha}(t)$.

Let $H\_n$ be the empirical entropy that you are looking for and $F(n, \alpha)$ be the value obtained when I replace $H(\frac{k}{n})$ with $f\_{\alpha}(\frac{k}{n})$.
We have

$F(n, \alpha) = n2^n \sum\_{k = 0}^{n} {n \choose k} f\_{\alpha}(\frac{k}{n})
= n 2^n 4^{\alpha} \sum\_{k = 0}^{n} {n \choose k} \left( \frac{k}{n} \right) ^ {\alpha} \left(1 - \frac{k}{n} \right) ^\alpha = n 4^{\alpha} E\left[\left( \frac{k}{n} - \frac{k^2}{n^2} \right)^{\alpha} \right] = n2^n 4^{\alpha} \sum\_{k = 0}^{n / 2} {n \choose k} \left(\frac{k}{n} \right)^{2 \alpha}$

For $\alpha = 1$, we know $F(n, \alpha) \le H\_n$ and direct evaluation says that $F(n, 1) = n - 1$, which is true for all $n$.

For $\alpha = 0.5$, we know $F(n, \alpha) \ge H\_n$ and a direct evaluation leads to $F(n, 0.5) = n 4^{0.5} E[\frac{k}{n}] = n$.

Therefore, for all $n > 0$, $n\ge H\_n \ge n - 1$.

I found it nontrivial to try this for any $\alpha < 1.0$ other than $\alpha = 0.5$.


---

