IID and two-state Markov entropy rates

For fair IID bits, every length-$n$ word has probability $2^{-n}$; hence $H_n=n$ and $h=1$ bit per symbol. The shift is stationary by product-law invariance, and [F4] gives expected LZ78 rate tending to one.

For the Markov source, take stationary law $\pi =(1\mathrm{/}2,1\mathrm{/}2)$ and transition matrix $K$ with diagonal entries $3\mathrm{/}4$ and off-diagonal entries $1\mathrm{/}4$; direct multiplication gives $\pi K=\pi$. Its length-$n$ block probabilities are $P(X_0^{n-1}=x_0^{n-1})=\frac{1}{2}{\prod }_{i=1}^{n-1}{K}_{x_{i-1},x_i}\mathrm{.}$ Expanding the finite entropy sum with this factorization gives $H_n=H(X_0)+{\sum }_{i=1}^{n-1}H(X_i\mid X_{i-1})=1+(n-1)H_2(1\mathrm{/}4),$ where $H_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$. Thus $h=H_2(1\mathrm{/}4)\approx 0.811278$. The stationary LZ78 expected-rate theorem [F4] gives the same limiting rate without an ergodicity assumption.

The distinct rates arise because IID entropy counts each bit without context, while the Markov transition entropy conditions on the previous state. Both examples have positive entropy, and the computed limits are consistent with $0\le h\le 1$.