Higher order empirical entropy is not the entropy of the empirical distribution?

Question

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

$ $

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

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