Entropy Rate of a Markov Chain

Per-symbol entropy of a dependent source as a stationary-weighted average of row entropies.

The idea

The entropy rate of a source is the long-run average information it produces per symbol.

For a source emitting independent symbols, the entropy rate is the entropy of a single symbol. A source with memory produces less: when the symbols already emitted narrow down the next one, each new symbol carries less information than it would alone, and the entropy rate accounts for this.

For a Markov chain the current state summarizes the entire past, which makes the computation short. Let $P$ be the transition matrix, $P_{ij} = \mathbb{P}(X_{n+1} = j \mid X_n = i)$, and let $\mu$ be a stationary distribution for it. From state $i$ the next symbol is drawn from row $i$ of $P$, so it carries that row's entropy,

$H(\text{row}_{i}) = -\sum_{j} P_{ij} \log_{2} P_{ij} \ \text{bits}.$

In the long run the chain spends a fraction $\mu_{i}$ of its time in state $i$, so the entropy rate averages the row entropies with those weights:

$H = \sum_{i} \mu_{i}\, H(\text{row}_{i}) \ \text{bits per symbol}.$

The weights matter: rows differ in how predictable they are, and each state contributes in proportion to how often the chain visits it, so the unweighted average of the row entropies is generally the wrong number.

Ways to work on it

• Walkthrough. Row entropies, stationary weighting, and why dependence lowers the rate.
• Practice. Set up the entropy rate of a symmetric two-state chain.
• Hardest. Compute the entropy rate of an asymmetric two-state chain.

Not sure where to start? Take the ten-question placement test.