Higher order empirical entropy is not the entropy of the empirical distribution? 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$.
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$.