Expected empirical entropy

Question

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.

Answer 1

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) \ .$$

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 @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.

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. 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.

Answer 2

(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.

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}

Answer 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.

Answer 4

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$.