Markov information source

A Markov information source uses a stationary finite Markov chain to emit symbols. The emitted symbol can be a function of the state. If it does not identify that state, the observed sequence need not itself be a Markov chain. The examples here use a fully observed Markov source, which makes the next-symbol uncertainty directly computable from the transition matrix.

Each emitted symbol identifies the state of a stationary finite Markov chain. Here the alphabet is the state space itself. Its transition matrix $P$ and stationary distribution $\pi$ determine the entropy rate of a fully observed Markov source.

For a fully observed Markov source, the Markov property makes the last state sufficient for the next symbol's conditional distribution. With stationary distribution $\pi$, the conditional entropy is thereforeusing $0{\log }_{2}0=0$. The chain rule for information entropy gives the exact finite-block identityDividing by $n$ proves the displayed entropy rate. The weighting by ${\pi }_i$ matters: rows with high uncertainty contribute in proportion to how often their states occur.

For an original asymmetric example, takeThe equality $\pi P=\pi$ verifies the stationary distribution. The single-symbol information entropy is $h_2(1/4)\simeq 0.81127812$, whereasThis formula describes observed states. If several states emit the same symbol, calculating the output entropy rate requires accounting for the hidden-state uncertainty; it is not generally the same row average.

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.

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.