= Binary Markov source
Take the <alphabet> $\{0,1\}$, fair initial <bit> $X_1$, and <transition matrix>
$$
P=\begin{pmatrix}1-q&q\\q&1-q\end{pmatrix},\qquad 0\leq q\leq1.
$$
The <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)$. Thus
$$
H(X_n)=1,\qquad H(X_n\mid X_1,\ldots,X_{n-1})=h_2(q)\quad(n\geq2),\qquad
\boxed{h(X)=h_2(q).}
$$
At $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)\simeq0.45643556$ <bits>. This is useful structure even though the single-symbol counts reveal no bias.
\Image[/entropy-rate-binary-source-and-innovations.png]
{title=A persistent fair-bit source reveals its new randomness through the flip sequence}
{description=Original simulated <sample paths> with a fixed random seed. The top row is a stationary <binary Markov source> with $q=1/8$; the middle row records <innovations in a binary Markov source>, marking whether each symbol differs from its predecessor. The bottom row is an independent fair-bit comparison. The marginal theoretical <probabilities> are $1/2$ for both displayed source processes; finite empirical counts need not be exactly equal. These traces illustrate the stipulated models and are not measured data or a proof of the <entropy rate>.}
At $q=0$, the random initial <bit> is repeated forever; at $q=1$, it alternates forever. Both have $H(X_1,\ldots,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.
Back to article page
