 Binary Markov source

Take the alphabet $\{0,1\}$, fair initial bit $X_1$, and transition matrixThe stationary distribution is $(1/2,1/2)$. Every emitted symbol is a fair bit, while the next symbol flips the previous one with probability $q$. For $q<1/2$, repeating the previous symbol is the better one-step prediction; for $q>1/2$, predicting its opposite is better. The resulting minimum next-symbol error probability is $\min (q,1-q)$, compared with $1/2$ when no history is used.

Given either state, the next-symbol information entropy is $h_2(q)$. ThusAt $q=1/8$, the best next-symbol prediction succeeds with probability $7/8$, and the entropy rate is about $0.54356444$ bits per symbol. The adjacent symbols share mutual information $I(X_1;X_2)=1-h_2(q)\simeq 0.45643556$ bits. This is useful structure even though the single-symbol counts reveal no bias.

At $q=0$, the random initial bit is repeated forever; at $q=1$, it alternates forever. Both have $H(X_1,\dots ,X_n)=1$ and zero entropy rate. At $q=1/2$, the symbols are independent and identically distributed fair bits, giving entropy rate one. Zero rate therefore need not mean that the initial choice was deterministic.