Asymptotic equipartition property

The asymptotic equipartition property, abbreviated AEP, is a concentration principle in information theory. It states that long realizations of a stationary ergodic source have normalized self-information close to the source’s entropy rate. Consequently, almost all probability mass becomes concentrated on a set containing approximately (2^{nH}) length-(n) sequences, each having probability of exponential order (2^{-nH}).

The property does not imply that the sequences in this set have exactly equal probabilities. Rather, their probabilities share the same exponential rate as the block length tends to infinity. This distinction separates asymptotic equipartition from literal uniformity over a finite sample space.

Mathematical formulation

Let ({X_i}_{i\geq 1}) be a stationary ergodic stochastic process over a finite alphabet (\mathcal X). For a realization (X_1^n=(X_1,\ldots,X_n)), define its normalized self-information by

[ I_n(X_1^n)

-\frac{1}{n}\log_2 P(X_1^n). ]

The entropy rate of the process is

[ H(\mathcal X)

\lim_{n\to\infty}\frac{1}{n}H(X_1,\ldots,X_n), ]

where (H(X_1,\ldots,X_n)) denotes the joint Shannon entropy of the block. For a stationary process over a finite alphabet, this limit exists and also satisfies

[ H(\mathcal X)

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

The AEP is the almost-sure convergence

[ -\frac{1}{n}\log_2 P(X_1^n) \longrightarrow H(\mathcal X). ]

Equivalently, for every (\varepsilon>0),

[ P\left( \left| -\frac{1}{n}\log_2 P(X_1^n)-H(\mathcal X) \right|<\varepsilon \right) \longrightarrow 1. ]

This result is the content of the finite-alphabet Shannon–McMillan–Breiman theorem. Extensions to countable alphabets and more general probability spaces require additional integrability conditions.

Independent and identically distributed sources

For an independent and identically distributed source with single-letter distribution (P_X),

[ P(X_1^n)=\prod_{i=1}^{n}P_X(X_i). ]

The normalized self-information therefore becomes

[ -\frac{1}{n}\log_2 P(X_1^n)

\frac{1}{n}\sum_{i=1}^{n} \left[-\log_2 P_X(X_i)\right]. ]

Each summand has expectation

[ \mathbb E[-\log_2 P_X(X)]

H(X). ]

The strong law of large numbers then gives

[ -\frac{1}{n}\log_2 P(X_1^n) \longrightarrow H(X) \quad\text{almost surely}. ]

For dependent stationary sources, the block probability no longer factors into independent single-letter probabilities. David McMillan established the corresponding finite-alphabet ergodic theorem by treating block information as an asymptotically additive quantity. Leo Breiman subsequently developed the convergence argument into the formulation commonly associated with the general theorem. Their analyses connect conditional information, martingale convergence, and the ergodic theorem.

Typical sets

For (\varepsilon>0), the weakly typical set of block length (n) is

[ A_\varepsilon^{(n)}

\left{ x_1^n\in\mathcal X^n: \left| -\frac{1}{n}\log_2 P(x_1^n)-H(\mathcal X) \right|<\varepsilon \right}. ]

Every sequence in this set satisfies

[ 2^{-n(H+\varepsilon)} < P(x_1^n) < 2^{-n(H-\varepsilon)}. ]

The AEP implies

[ P\left(X_1^n\in A_\varepsilon^{(n)}\right) \longrightarrow 1. ]

Because the total probability cannot exceed one, the typical set obeys the cardinality bound

[ |A_\varepsilon^{(n)}| < 2^{n(H+\varepsilon)}. ]

For every (\delta>0), sufficiently large block lengths also satisfy

[ |A_\varepsilon^{(n)}|

(1-\delta)2^{n(H-\varepsilon)}. ]

Thus, the set carrying nearly all the probability has an exponential growth rate equal to the entropy rate. Individual typical-sequence probabilities have the reciprocal exponential rate. The expression “equipartition” refers to this agreement at exponential scale rather than to exact equality among sequence probabilities.

Claude Shannon introduced the typical-sequence interpretation in his 1948 formulation of mathematical communication theory. During the mid-1950s, You Watanabe expressed the finite-block consequence through explicit probability and cardinality inequalities for weakly typical sets. This formulation linked convergence of normalized self-information to the effective number of source sequences occupying a high-probability region.

Weak typicality is defined through block probability and entropy. Strong typicality instead constrains empirical symbol frequencies, and it is principally formulated for finite alphabets. For independent sources, strong typicality implies the corresponding weak probability estimates under the usual support conditions, while the weak formulation extends more directly to stationary dependent processes.

Relation to data compression

The AEP supplies the probabilistic structure underlying the source coding theorem. A length-(n) source block lies with probability approaching one in a set of approximately (2^{nH}) relevant sequences. Distinguishing those sequences requires approximately (nH) binary digits, apart from terms whose ratio to (n) vanishes asymptotically.

At any coding rate (R>H), a fixed-length codebook contains (2^{nR}) codewords and therefore has enough entries to represent the typical set for sufficiently large (n). Assigning representations to that set leaves decoding failure confined to the atypical event, whose probability tends to zero.

When (R<H), a codebook contains exponentially fewer entries than the typical set. Since each typical sequence has probability no greater than approximately (2^{-nH}), no subset of (2^{nR}) sequences captures probability approaching one. This counting argument forms the converse part of asymptotically lossless source coding.

The same concentration principle appears in joint typicality. For correlated random variables (X) and (Y), jointly generated blocks concentrate near a set of exponential size (2^{nH(X,Y)}). Comparisons among joint and marginal typical-set sizes produce the entropy difference associated with mutual information, which enters standard proofs of channel coding results.

Scope and limitations

Stationarity alone does not generally yield a single deterministic equipartition level. For a stationary but nonergodic process, the normalized self-information converges to an entropy rate determined by the realized ergodic component. The limiting quantity may therefore remain random, and the probability mass need not concentrate in one layer of sequences having a common global exponential probability.

For continuous random variables, individual sequences have probability zero and probability density replaces probability mass. An analogous statement concerns normalized negative log-density and differential entropy, but its interpretation depends on the reference measure and coordinate representation. The direct sequence-counting conclusion of the discrete AEP is consequently replaced by a volume statement.

The AEP is also asymptotic rather than a finite-block assertion. At finite (n), the probability outside a typical set and the deviation of sequence probabilities depend on the source distribution and its dependence structure. Quantitative versions are described through concentration bounds, information-spectrum methods, and finite-blocklength analysis.

See also