Asymptotic equipartition property ($-n^{-1}{\log }_{2}P(X^n)\to H(X_1)$)

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,\dots$ on a finite alphabet, let $p$ be their probability mass function and $H=\mathbb{E}[-{\log }_{2}p(X_1)]$. ThenHere $P(X_1,\dots ,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: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.^[ref]

Take an IID random variable source of bits with $P(X_j=1)=1/4$. Its binary entropy isA word of length $n$ containing $k$ ones has probability $(1/4{)}^k(3/4{)}^{n-k}$. Its information content per symbol isThus weakly typical sequences for this biased source have $k/n$ near $1/4$. With tolerance $\epsilon =0.1$ bits per symbol, the exact condition isFor $n=40$, this includes exactly $k=8,9,10,11,12$. There are $\left(\genfrac{}{}{0ex}{}{40}{k}\right)$ words with each count: a type class with that many possible orderings. Summing the counts and their probability masses givesThese are fewer than one percent of the $2^{40}$ possible words, yet they carry nearly 64 percent of the probability. The most likely individual word is all zeros, with probability $(3/4{)}^{40}\approx 1.006\times 10^{-5}$; it is outside this typical set. No contradiction is involved: the type classes near ten ones each contain many more individual words.

The count $K_n$ has binomial distribution with mean $n/4$ and variance $3n/16$. The information content per symbol is an affine function of $K_n/n$, so its variance isChebyshev's inequality therefore gives the finite-sample lower boundThe bound is often loose, but it proves that every fixed positive tolerance eventually captures nearly all the probability. Direct summation of the binomial distribution's probability masses gives $P(T_{0.1}^{(640)})\approx 0.999779$. A finite sample does not need to have a nearly full typical set: the 40-symbol example above captures only about $0.639$.

The typical sequence theorem turns a probability concentration into a coding construction. Assign one binary number index to each weakly typical sequence, plus a reserved index for every word outside the set. The decoder recovers every typical word exactly; the reserved index has one predetermined output. The block code usesbits and has reconstruction-error probability at most $1-P(T_{\epsilon }^{(n)})$.

For this example and $\epsilon =0.1$, $n=40$ needs 34 bits but permits error up to about $0.3611$. At $n=640$, 570 bits suffice and the error bound is about $0.0002215$. These are existence calculations for an explicitly enumerated collection, rather than claims about an efficient practical encoder. The reduction comes from protecting the whole high-probability collection, rather than just its single most likely member.

Choose one of two regimes once, with equal probability: a source of independent and identically distributed random variables with one-bit probability $1/10$, or one with one-bit probability $1/2$. Keep the chosen regime forever. The resulting source is a strictly stationary process, because shifting a block does not change either component law. It is not an ergodic stationary process: its limiting empirical frequency identifies the regime.

The source's information rate isConditioning on the single regime bit changes any block's information entropy by at most one bit, so dividing by the block length proves this rate. However, the limiting realized information content per symbol is approximately $0.468996$ in the first regime and one in the second. The alternative component's likelihood ratio decays exponentially along a typical path from the chosen component, at a rate given by the positive relative entropy between the two Bernoulli distributions. The mixture therefore has two possible pathwise limits, not one limit equal to the averaged information rate.

In A Mathematical Theory of Communication by Claude Shannon (1948, section 7), Claude Shannon explains that the common symbol counts in a long independent message make its negative logarithmic probability approximately the message length times the source entropy. Theorem 3 separates an exceptional collection of small total probability from messages with this normalized information cost; Theorem 4 relates the number needed to accumulate a fixed probability to the entropy. The finite-state source setting matters to the historical statement.^[ref]

For an IID source, the epsilon-typical set consists of words $u^n$ satisfying $|-(1/n)\log p(u^n)-H(U)|\le \epsilon$. Its probability tends to one, and its cardinality is at most $2^{n(H(U)+\epsilon )}$.

Let $A^{n,\epsilon }$ be the weak typical set of a finite alphabet independent and identically distributed source with Shannon entropy $H$, and let $B_n$ be any sets with $\mathrm{Pr}(X^n\in B_n)\to 1$. The asymptotic equipartition property and union bound give $\mathrm{Pr}(X^n\in A^{n,\epsilon }\cap B_n)\to 1$. Every word in the intersection has probability mass between $2^{-n(H+\epsilon )}$ and $2^{-n(H-\epsilon )}$. Summing these bounds givesFor every fixed $\delta >0$, the first probability eventually exceeds $2^{-\delta }$, proving the title bound. A sample mean within a fixed positive tolerance of the expected value supplies $B_n$ by the strong law of large numbers.

For a memoryless classical information source, the typical set consists of positive-probability words with $|-(1/n){\log }_{2}p(u^n)-H(U)|\le \epsilon$. The weak law of large numbers applied to $-{\log }_{2}p(U_j)$ proves its probability tends to one. Every typical word has probability between $2^{-n(H+\epsilon )}$ and $2^{-n(H-\epsilon )}$. Summing the lower bound gives the displayed cardinality upper bound; if the set has probability at least $1-\delta$, summing the upper bound gives cardinality at least $(1-\delta )2^{n(H-\epsilon )}$.

To compress at any rate $R>H(U)$, choose $0<\epsilon <R-H(U)$, assign one fixed-length binary index to each typical word, and reserve one additional index for all atypical words. At most $\lceil nR\rceil$ bits suffice for all large $n$. Decoding inverts the typical-word indices and makes an arbitrary output for the reserved index. The reconstruction error is at most the probability of the atypical set and tends to zero.

For an IID random variable source with probability mass function $p$, a word $x^n$ is weakly typical when $|-(1/n){\log }_{2}p(x^n)-H(X)|\le \epsilon$. It has probability on the scale $2^{-nH(X)}$. The weak law of large numbers makes the typical set probable, but does not make every word in it representative: for a uniform source every possible word is weakly typical.

For a typical set of probability at least $1-\delta$,The upper bound sums the lower probability bound for each word; the lower bound sums the upper probability bound and uses the set's total probability. These bounds turn the asymptotic equipartition property into exponential estimates of source-coding dimension.

For a finite-alphabet IID source and fixed $0<\epsilon <1$, the smallest set of length-$n$ strings carrying probability at least $1-\epsilon$ has size $2^{n(H(U)+o(1))}$. The typical set bounds give the upper estimate. For the lower estimate, any such set intersects the typical set in probability bounded away from zero, while each typical string has probability at most $2^{-n(H(U)-\delta )}$.

// Target: probability-and-statistics.bigb

For a finite-alphabet IID random variable source, a strongly typical word has empirical symbol frequencies within the chosen tolerance of every $p(x)$, and contains no zero-probability symbols. Unlike a weakly typical sequence, this definition controls the individual symbol counts. Both definitions give sets whose probability tends to one for fixed positive tolerance.