Entropy rate · aiwiki.page

In information theory, the entropy rate of a stochastic process is its long-run average Shannon entropy per observation. Unlike the entropy of a single symbol, it accounts for dependence across a sequence: individually unpredictable observations may become predictable when their history is known. Entropy rate therefore describes the average amount of new information supplied by successive observations and provides a fundamental benchmark for compressing sources with memory. (stanforddatacompressionclass.github.io)

Definition and units

Let $X_1,X_2,\ldots$ be discrete random variables, and write $X_1^n=(X_1,\ldots,X_n)$ . Their block entropy is

H(X_1^n) =-\sum_{x_1^n}p(x_1^n)\log_2 p(x_1^n),

where $p(x_1^n)$ is their joint probability distribution and $0\log_2 0$ is interpreted as zero. The entropy rate is

\overline H(X) =\lim_{n\to\infty}\frac{H(X_1^n)}{n},

provided the limit exists. It depends on the distribution of the entire process, not merely the distribution of an individual observation. (arxiv.org)

With base-two logarithms, its units are bits per symbol or observation. Natural logarithms instead give nats per observation. “Rate” here primarily means information per sequence position; converting it to information per second requires specifying the sampling interval. (www-ee.stanford.edu)

Stationarity and conditional uncertainty

For a stationary process on a finite alphabet, the entropy rate exists and has the equivalent expression

\overline H(X) =\lim_{n\to\infty} H(X_n\mid X_1,\ldots,X_{n-1}).

Here conditional entropy measures uncertainty remaining after the preceding observations are supplied. Stationarity makes these successive conditional entropies nonincreasing, while nonnegativity bounds them below. The entropy chain rule expresses block entropy as their sum, so their averages converge to the same limit. (www-ee.stanford.edu)

For a two-sided stationary process, this is also expressed as the entropy of the present conditional on the entire past:

\overline H(X)=H(X_0\mid X_{-1},X_{-2},\ldots).

In particular,

0\leq\overline H(X)\leq H(X_0).

Dependence can thus reduce the information generated per observation without changing the marginal entropy. Ergodicity is not required for existence in the stationary finite-alphabet setting, although it is important for relating ensemble quantities to individual observed sequences. (www-ee.stanford.edu)

Independent and Markov sources

If observations have statistical independence and share the same distribution, then

H(X_1^n)=nH(X_1), \qquad \overline H(X)=H(X_1).

For an independent binary source with Bernoulli distribution and success probability $p$ , this gives the binary entropy function

h_2(p)=-p\log_2p-(1-p)\log_2(1-p).

An independent fair binary source consequently generates one bit per symbol. (stanforddatacompressionclass.github.io)

For a stationary, finite-state Markov chain, the Markov property reduces the relevant history to the preceding state. If $P=(P_{ij})$ is its transition matrix and $\pi$ its stationary distribution, then

\overline H(X) =H(X_2\mid X_1) =-\sum_i\pi_i\sum_jP_{ij}\log_2P_{ij}.

Thus the rate is the expected value of the entropy of a transition row, weighted by the frequency of its starting state. (arxiv.org)

For example, consider a stationary binary chain that switches state with probability $q$ and remains unchanged otherwise. Substitution into this formula gives $\overline H(X)=h_2(q)$ , although its uniform marginal distribution has entropy one bit. At $q=0$ , the initial bit determines the entire constant sequence; at $q=1$ , it determines an alternating sequence. Both therefore have zero entropy rate despite their uncertain starting values. (arxiv.org)

Typical sequences and compression

The Shannon–McMillan–Breiman theorem states that, for a stationary ergodic finite-alphabet process,

-\frac1n\log_2p(X_1^n) \longrightarrow\overline H(X) \quad\text{[[almost-surely|almost surely]]}.

This is the dependent-source form of the asymptotic equipartition property. Long typical sequences have probabilities approximately $2^{-n\overline H(X)}$ , and a high-probability typical collection has size approximately $2^{n\overline H(X)}$ , with exponential tolerances understood. (cs.purdue.edu)

Together with source coding theorems, this gives entropy rate its operational meaning in lossless data compression: it is the asymptotic minimum average coding length per symbol for these sources. A compressor that ignores dependence generally targets marginal entropy instead. Arithmetic coding can exploit memory by coding each symbol using its conditional probability given preceding symbols. (cs.purdue.edu)

Computation and estimation

An explicitly specified finite-state Markov source allows direct calculation from $P$ and $\pi$ . For a hidden Markov model, however, the observed process generally has longer memory than the underlying state process. Its entropy rate need not admit the simple transition-row formula. Bounds, filtering-based representations, numerical approximation, and simulation are used to address this difficulty. (web.stanford.edu)

Estimating entropy rate from a finite time series is a different problem from calculating it for a known source. For Markov data, one approach estimates state frequencies and transition probabilities, then substitutes them into the formula. Large state spaces and limited observations create significant estimation error; rigorous sample-complexity results depend on assumptions about the chain’s dependence and mixing. (arxiv.org)

For language data, the rate concerns uncertainty after context is taken into account, rather than frequencies of isolated words. Research connecting entropy-rate estimation to language modeling also relates it to perplexity. Such applications must distinguish a source’s entropy rate from the predictive performance of a particular fitted model. (arxiv.org)

References

Entropy and Information Theorywww-ee.stanford.edu
Non IID Sources and Entropy Ratestanforddatacompressionclass.github.io
Analytic Pattern Matching: From DNA to Twittercs.purdue.edu
Entropy Rate Estimation for Markov Chains with Large State Spacearxiv.org
Approximations for the Entropy Rate of a Hidden Markov Processweb.stanford.edu