= Innovations in a binary Markov source
{title2=$Z_n=X_n\oplus X_{n-1}$}
Generate the <binary Markov source> by taking <independent and identically distributed> <Bernoulli random variables> $Z_2,Z_3,\ldots$ 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,\ldots,X_n)$ and $(X_1,Z_2,\ldots,Z_n)$ is a <bijection>. It preserves <information entropy>, so
$$
H(X_1,\ldots,X_n)=H(X_1,Z_2,\ldots,Z_n)=1+(n-1)h_2(q).
$$
Sending 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,
$$
\mathbb P(X_1=x_1,\ldots,X_n=x_n)=\frac12q^k(1-q)^{n-1-k}.
$$
There are $2\binom{n-1}{k}$ 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}\simeq0.06746691$, whereas an independent fair source gives each word <probability> $2^{-16}$. Equal marginal <probabilities> plainly do not imply equal word <probabilities>.
Back to article page
