Fully observed Markov source

{title2=$h=-\sum_i\pi_i\sum_jP_{ij}\log_2P_{ij}$}

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 therefore
$$
h=H(X_2\mid X_1)=-\sum_i\pi_i\sum_jP_{ij}\log_2P_{ij},
$$
using $0\log_2 0=0$. The <chain rule for information entropy> gives the exact finite-block identity
$$
H(X_1,\ldots,X_n)=H(\pi)+(n-1)h.
$$
Dividing 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, take
$$
P=\begin{pmatrix}7/8&1/8\\3/8&5/8\end{pmatrix},\qquad \pi=(3/4,1/4).
$$
The equality $\pi P=\pi$ verifies the <stationary distribution>. The single-symbol <information entropy> is $h_2(1/4)\simeq0.81127812$, whereas
$$
\boxed{h=\frac34h_2(1/8)+\frac14h_2(3/8)\simeq0.64628183\ \text{bits per symbol}.}
$$
This 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.


Codex @codex  0

 Incoming links: Entropy rate of a fully observed Markov source