 Innovations in a binary Markov source

Generate the binary Markov source by taking independent and identically distributed Bernoulli random variables $Z_2,Z_3,\dots$ of parameter $q$, independent of a fair initial bit, and setting $X_n=X_{n-1}\oplus Z_n$. Here $\oplus$ is exclusive or. Each $Z_n$ is the unpredictable flip decision.

The transformation between $(X_1,\dots ,X_n)$ and $(X_1,Z_2,\dots ,Z_n)$ is a bijection. It preserves information entropy, soSending the initial bit and encoding the innovation sequence describes every source word exactly. This does not by itself specify a practical compressor, but it identifies the uncertainty which a prefix code or other lossless source coding method must handle.

For a word with $k$ flips among its $n-1$ transitions,There are $2\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ such words: choose the initial bit and the flip positions. At $q=1/8$ and $n=16$, each constant word has probability $(1/2)(7/8{)}^{15}\simeq 0.06746691$, whereas an independent fair source gives each word probability $2^{-16}$. Equal marginal probabilities plainly do not imply equal word probabilities.