7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't see a question here. $\endgroup$ – Suresh Venkat Apr 7 '14 at 17:36
  • $\begingroup$ Is the equation above true? Can anybody prove it respectively prove that the equation doesn't hold? $\endgroup$ – Danny Apr 7 '14 at 17:38
  • $\begingroup$ you have a bunch of equations. it would be better to number them. also highlight the question with ">" blockquoting. $\endgroup$ – vzn Apr 8 '14 at 15:20
  • $\begingroup$ I edit my question from $\varepsilon_{n}\rightarrow0$ to $\varepsilon_{n}\rightarrow c$, where $c$ is a constant. $\endgroup$ – Danny Apr 9 '14 at 13:46
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Danny Apr 10 '14 at 10:08
  • $\begingroup$ *converges instead of "converts" :) $\endgroup$ – Danny Apr 10 '14 at 11:29
  • $\begingroup$ 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. $\endgroup$ – mobius dumpling Apr 10 '14 at 13:30
  • $\begingroup$ This seems like the better answer to accept in my opinion too! Very nice/elegant entropy argument. $\endgroup$ – usul Apr 15 '14 at 18:10
  • 2
    $\begingroup$ Note that in the literature you'll often see $\log_2\sqrt{e}$ written as $\frac{1}{2\ln 2}$. $\endgroup$ – Steven Stadnicki Apr 18 '14 at 18:52
4
$\begingroup$

(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

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}

$\endgroup$
  • $\begingroup$ 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.. $\endgroup$ – Danny Apr 8 '14 at 21:35
  • $\begingroup$ @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). $\endgroup$ – usul Apr 9 '14 at 1:24
  • $\begingroup$ 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}$? $\endgroup$ – Danny Apr 9 '14 at 13:35
  • $\begingroup$ @Danny, I'm not sure how to get this with a shorter proof, but maybe another answer will do so. $\endgroup$ – usul Apr 9 '14 at 20:51
  • $\begingroup$ Thanks again for your help. Everything seems to be clear.. $\endgroup$ – Danny Apr 10 '14 at 9:07
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Danny Apr 8 '14 at 15:06
  • $\begingroup$ 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. $\endgroup$ – Danny Apr 8 '14 at 15:18
  • $\begingroup$ 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)$. $\endgroup$ – usul Apr 9 '14 at 1:26
  • $\begingroup$ @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)$). $\endgroup$ – mobius dumpling Apr 9 '14 at 11:39
  • $\begingroup$ @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. $\endgroup$ – mobius dumpling Apr 9 '14 at 11:44
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.