Basically, the problem is that I always thought that the (unnormalized) $k$th order empirical entropy $n\cdot H_k(x)$ (see "Backround" at the end of this post for more information) for a given string $x$ of length $n$ equals the entropy of the empirical distribution on the set of all words of length $n$ (the conditional probabilities are taken from the observed occurrences in $x$). Until today, I was totally sure that this is true, but it seems to be wrong for very easy examples (e.g. for $x=1011$).

To be more accurate, consider $\Sigma=\{0,1\}$, $x=1011$ and $k=1$ such that $$n\cdot H_k(x)=4\cdot H_1(x)=2.$$ On the other hand, the corresponding empirical distribution is a First-order Markov source described by

  • $P(\text{The first letter is }0)=0$
  • $P(\text{The first letter is }1)=1$
  • $P(\text{Letter }0 \text{ immediately follows after letter }0)=0$
  • $P(\text{Letter }1 \text{ immediately follows after letter }0)=1$
  • $P(\text{Letter }0 \text{ immediately follows after letter }1)=0.5$
  • $P(\text{Letter }1 \text{ immediately follows after letter }1)=0.5$

Now this probabilities yield a random variable $X$ on words of length $n=4$, where the Shannon entropy is $$H(X)=-\sum_{w\in\Sigma^4}P(w)\log P(w)=\frac{9}{4}.$$ (You only need to consider words of length $4$ which start with $1$ and do not contain $00$.)

But shouldn't be both measures intuitively give the same value? I did the calculations more than once, so I am pretty sure the mistake is in my understanding, not in the calculation. Or did I always thought something wrong? But it seems so clear that the empirical entropy is the entropy of the empirical distribution (also for higher order Markov sources).

$ $

$ $
For a given string $x\in\Sigma^n$ over an alphabet of size $k$, the ($0$-th order) empirical entropy is defined as $$H_0(x)=\frac{1}{n}\sum_{i=1}^{k}n_i\cdot\log \frac{n}{n_i},$$ where $n_i$ is the number of occurrences of the $i$th alphabet symbol. The $k$-order empirical entropy ($k\ge 1$) is then defined as $$H_k(x)=\frac{1}{n}\sum_{|w|=k}|S_w|H_0(S_w),$$ where $S_w$ is the string obtained by concatenating the characters immediately following occurrences of $w$ in $x$.


1 Answer 1


No, as your counterexample shows, it is not true. I don't understand why you previously thought it was true, either, so it's hard to say what might have gone wrong with your previous intuition.

We can say that

$$H(X) = H(X_1) + H(X_2 | X_1) + H(X_3 | X_1,X_2) + H(X_4 | X_1,X_2,X_3),$$

where $X_i$ denotes the $i$th character in $X$. that much is true.

In the example you gave, $H(X_1) = 0$, $H(X_2|X_1) = 1$, $H(X_3|X_1,X_2) = 0.5$, $H(X_4 | X_1,X_2,X_3) = 0.75$ (see footnote * for explanation). Thus $H(X) = 1 + 0.5 + 0.75 = 2.25$.

Do notice that $\Pr[X_i=1]$ and $H(X_{i+1}|X_1,\dots,X_i)$ both depend on $i$. This might be important.

Also, notice that $H(X_{i+1}|X_1,\dots,X_i)$ is unrelated to $H_1(x)$.

Perhaps you were expecting $\Pr[X_i=1]$ and $H(X_{i+1}|X_1,\dots,X_i)$ to be the same for all $i$? If that were true, there might be a relationship between $H_1(x)$ and $\Pr[X_i=1]$ and $H(X_{i+1}|X_1,\dots,X_i)$ (or something similar to them)... but it's not.

Footnote *: How did I calculate those? I used the formula

$$H(X_{i+1}|X_1,\dots,X_i) = \sum_v \Pr[(X_1,\dots,X_i) = v] \times H(X_{i+1}|(X_1,\dots,X_i) = v).$$

For $i=1,2$, we only need to consider two values of $v$; for $i=3$, we only need to consider three values of $v$.

  • $\begingroup$ Thanks for your answer. I think my confusion is based on the fact that for the $0$th order empirical entropy, this is true, i.e. the empirical entropy is the Shannon entropy of the empirical distribution. So I thought it is true also for higher order Markov sources. $\endgroup$
    – Danny
    May 10, 2017 at 8:59
  • $\begingroup$ Also, Paul Vitányi states in his paper "On empirical entropy" on side 5 that the Shannon entropy of the random variable $X$ "associated with the $k$th order empirical entropy computed from $x$" equals $n\cdot H_k(x)$. Do you have an idea which distribution on the set of words of length $n$ he could mean, i.e. which natural distribution on $ \Sigma^n$ yields the Shannon entropy $n\cdot H_k(x)$ for $x\in\Sigma^n$ ? I always thought he refers to the empirical distribution as described in my question. $\endgroup$
    – Danny
    May 10, 2017 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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