= Asymptotic equipartition property
{title2=$-n^{-1}\log_2 P(X^n)\to H(X_1)$}
{wiki}
= AEP
{c}
{synonym}
The <asymptotic equipartition property> explains why a long message from a source can usually be described using its <information entropy> per symbol. Individual messages can have very different <probabilities>, but the messages carrying almost all the total <probability> have similar logarithmic costs per symbol. The <Bernoulli typical-set example> makes the distinction between an individual message and a large collection explicit.
For <independent and identically distributed random variables> $X_1,X_2,\ldots$ on a <finite alphabet>, let $p$ be their <probability mass function> and $H=\mathbb E[-\log_2p(X_1)]$. Then
$$
\boxed{-\frac1n\log_2P(X_1,\ldots,X_n)\longrightarrow H\quad\text{almost surely}.}
$$
Here $P(X_1,\ldots,X_n)$ means the <probability mass> of the realized word, evaluated under the source law. The product rule for <independent random variables> turns its <information content> into a sum:
$$
-\frac1n\log_2P(X_1,\ldots,X_n)
=\frac1n\sum_{j=1}^n[-\log_2p(X_j)].
$$
The <strong law of large numbers> gives the limit. Zero-probability symbols do not occur; on the positive-probability support of a <finite alphabet>, these information costs are finite. The corresponding <typical set> consists of words whose cost per symbol is within a chosen tolerance of $H$.
For a <strictly stationary process> with a <finite alphabet>, the constant-limit extension requires <ergodicity>. The <Shannon-McMillan-Breiman theorem> then replaces the one-symbol <information entropy> with the <information rate>. <Stationarity without ergodicity in an information source> shows why stationarity alone is insufficient.<6.441 Information Theory (Spring 2016 lecture notes) by Yury Polyanskiy and others>[§8, Theorem 8.1 and Corollary 8.2, printed p. 90: stationary ergodic sources and typical sets]{ref}
Back to article page
