Entropy Rate of a Markov Source and the Value of Context

A frequency table over bytes describes a source that emits each symbol independently. Most real sources do not: the next character in a text depends on the previous one, the next pixel in an image depends on its neighbours, and the next value in a time series depends on recent values. Coding such a source with a symbol-frequency model leaves the dependence uncoded, and the gap between what the model achieves and what the source allows is exactly the quantity that a context model recovers.

The rate is a limit of joint entropies

For a stochastic process $X_1, X_2, \ldots$, the entropy of the first $n$ symbols is $H(X_1, \ldots, X_n)$, and the per-symbol cost grows with $n$ in a way that does not converge to the marginal entropy. The entropy rate is defined as the limit

$$H(\mathcal{X}) = \lim_{n \to \infty} \frac{1}{n} H(X_1, \ldots, X_n)$$

when it exists, which it does for stationary processes. The limit exists because the joint entropy of a stationary process is subadditive: $H(X_{1..n+m}) \le H(X_{1..n}) + H(X_{n+1..n+m})$ by the chain rule and the fact that conditioning cannot increase entropy. Dividing by $n+m$ and applying Fekete’s lemma to the sequence $H(X_1, \ldots, X_n)$ gives convergence of the normalized sequence.

For a stationary first-order Markov chain, the joint entropy decomposes by the chain rule into $H(X_1) + \sum_{i=2}^{n} H(X_i \mid X_{i-1})$, and every term after the first is the same conditional entropy, so $\frac{1}{n}H(X_1,\ldots,X_n)$ tends to $H(X_2 \mid X_1)$ as $n$ grows, the first term being divided by $n$ and vanishing:

$$H(\mathcal{X}) = \sum_{i} \pi_i \sum_{j} P_{ij} \log_2 \frac{1}{P_{ij}}$$

where $\pi$ is the stationary distribution of the transition matrix and $P_{ij}$ the transition probabilities. The stationary distribution is required, not optional: the chain’s long-run symbol frequencies determine how often each row of the matrix is used, and using uniform weights instead gives the wrong answer.

The gap between $H(X_2 \mid X_1)$ and $H(X_1)$ is the mutual information between consecutive symbols, and it is the entire saving available from an order-1 model. If consecutive symbols were independent, the conditional entropy would equal the marginal entropy and there would be no saving; if the chain were deterministic, the conditional entropy would be zero and the sequence would be fully predictable from its first symbol.

A worked chain

Take a two-state chain with transition matrix rows $(0.9, 0.1)$ and $(0.2, 0.8)$. The stationary distribution solves $\pi_1 = 0.9\pi_1 + 0.2\pi_2$ with $\pi_2 = 1 - \pi_1$, giving $\pi_1 = 2/3$ and $\pi_2 = 1/3$. The two row entropies are

$$H(0.9, 0.1) \approx 0.469 \text{ bits}, \qquad H(0.2, 0.8) \approx 0.722 \text{ bits}$$

and the entropy rate is $\tfrac23(0.469) + \tfrac13(0.722) \approx 0.553$ bits per symbol. The marginal distribution is $(2/3, 1/3)$, whose entropy is about 0.918 bits. The order-0 model therefore overstates the cost by roughly 0.365 bits per symbol, about 40 percent above the rate, purely by ignoring the dependence between adjacent symbols.

Note the asymmetry between the row entropies. The state that is visited two-thirds of the time is also the one with the more predictable transition, and the rate weights each row by its visit frequency rather than averaging the two entropies equally. This is the mistake that a naive “average of row entropies” makes, and it is a common error when computing rates for a chain given only as a matrix.

import math

def entropy_rate(P, pi):
    """P[i][j] transition probabilities; pi stationary distribution."""
    total = 0.0
    for i, p in enumerate(pi):
        if p == 0.0:
            continue
        row = 0.0
        for q in P[i]:
            if q > 0.0:
                row -= q * math.log2(q)
        total += p * row
    return total

P = [[0.9, 0.1], [0.2, 0.8]]
pi = [2/3, 1/3]
print(entropy_rate(P, pi))   # 0.5533

The function assumes the chain is irreducible and aperiodic so that the stationary distribution is unique; for a chain with multiple recurrent classes the “stationary distribution” is not unique and the entropy rate depends on which class the process is in, so the rate is not a single number.

Context models in practice

A context model conditions each symbol on the preceding $k$ symbols, which is an order-$k$ Markov model over the alphabet. The single-symbol entropy that such a model replaces is the quantity defined in Shannon Entropy as the Expected Cost of an Outcome, and the difference between the two is exactly what the context buys. For bytes, the number of contexts is $256^k$, so a full table is impossible beyond $k=2$; the practical approach is to store only contexts that have been observed, in a hash table or a trie, and to fall back to shorter contexts when a long one has too few counts.

That fallback is the core idea of prediction by partial matching. The encoder tries the longest available context first; if the symbol has been seen there, it codes it with that context’s counts; if not, it emits an escape symbol and retries with the next shorter context, down to order $-1$ where all symbols are equally likely. The escape mechanism is what makes the model well-defined for unseen symbols, and the escape probability estimate determines how much the model pays for novelty. A common estimate sets the escape count to the number of distinct symbols that have been seen in the context, so a context that has produced many different symbols reserves more probability for novelty. PPM variants differ mainly in this choice, since it fixes how much probability the model reserves for the novel case.

The design trade-off is between model specificity and statistical reliability. A long context has a sharply peaked distribution, which is cheap when it is accurate, but it is estimated from few samples and is often wrong. A short context is well estimated but less informative. The escape hierarchy lets each symbol be coded at whichever level has enough evidence, which is why PPM variants outperform fixed-order models on text despite having no more information available.

The memory cost is real. Storing counts for every observed context at order 5 over bytes requires a node per context, and the total number of nodes is bounded by the input size times the order, since each position creates at most one new context. A trie with $n \cdot k$ nodes is manageable for a file but not for a stream that must run in a fixed memory budget; pruning, hashing with collisions, and bounded-depth models are the usual responses.

Why the entropy rate bounds compression of dependent data

The source-coding theorem for a stationary ergodic source states that the entropy rate is the infimum of achievable rates, exactly as the order-0 entropy is for an i.i.d. source. The direct part uses typical sequences of the process, whose probability is approximately $2^{-nH(\mathcal{X})}$ for large $n$, and the converse shows that no code can do better. The practical consequence is that an order-$k$ model can approach the order-$k$ entropy rate but not the true rate if the source has longer memory, and the difference between them is not recoverable by better entropy coding of the same model.

This is why the choice of model matters more than the choice of coder. Arithmetic coding achieves the model’s ideal length plus a constant; the model’s distance from the true source determines the rate actually obtained. A context-mixing compressor that combines predictions from several orders, as in the PAQ family, is exploiting exactly this: the combination is a way of estimating the conditional distribution of the next symbol given all available contexts, rather than committing to one order.

There is a further theoretical point that is often missed. The entropy rate is a property of the process, and a model class that does not contain the process cannot achieve it no matter how much data is available. Finite-order Markov models cannot represent sources with unbounded memory, such as a process whose symbol at position $n$ depends on the symbol at position $n/2$. Universal coding handles this by allowing the model order to grow with the data, paying a model cost that grows like $\tfrac{k}{2}\log_2 n$ bits for $k$ parameters, which is the leading term in the minimum description length penalty discussed in Kolmogorov Complexity, Incompressibility, and Minimum Description Length.

Conditions that break the formulas

Three conditions break the simple formulas.

Nonstationarity. The entropy rate is defined for a stationary process. For a source whose statistics drift, the relevant quantity is a time-varying rate, and a model estimated over the whole stream is an average that is wrong at both ends. Block-adaptive models reset or decay counts to track the drift, at the cost of estimation noise.

Periodicity. A periodic chain is not itself stationary, so the entropy rate must be read as a Cesàro limit: the average over one period of the chain equals the stationary-weighted rate, so the formula still gives the long-run average. The per-step cost, however, depends on the phase, and a code that assumes a constant rate will be systematically off within each period.

Finite-precision counts. Adaptive models must rescale counts before they overflow the coder’s state, and the rescaling changes the estimated distribution. With a 16-bit total, counts can accumulate up to 65536 observations before they must be halved, and the halving loses the least significant bit of every count. For a context with a few observations the loss is a rounding difference; for one with tens of thousands the halving changes the relative weights slightly, which shifts the coded length by a small amount in either direction depending on the model and the rescaling rule.

The practical summary is that the entropy rate states what the source allows, while the context structure states what a given model can see. The gap between the two is not an implementation defect; it is the model class’s distance from the source, and closing it requires a richer model rather than a better entropy coder.