Typical Sequences and AEP — Mathematics Knowledge System

Overview

The Asymptotic Equipartition Property (AEP) states that for i.i.d. sequences X_1,...,X_n, the sample entropy -(1/n)log p(X_1,...,X_n) converges in probability to H(X). Typical sequences have probability approximately 2^{-nH(X)} each, and there are approximately 2^{nH(X)} of them. This explains why H(X) bits per symbol is sufficient (and necessary) for lossless compression.

Intuition

If you flip a fair coin 1000 times, you expect about 500 heads. Sequences with roughly 500 heads are 'typical.' There are about 2^{1000*H(1/2)} = 2^{1000} such sequences (all of them for a fair coin). For a biased coin (p=0.9 heads), typical sequences have about 900 heads, and there are only about 2^{1000*H(0.9)} ≈ 2^{469} of them -- much fewer than 2^{1000} total. Compression works because you only need to encode the typical ones.

Formal Definition

Definition

AEP (weak law): for i.i.d. X_i ~ p(x): -(1/n)log p(X_1,...,X_n) -> H(X) in probability. The typical set T_epsilon^{(n)}: sequences where |-(1/n)log p(x^n) - H(X)| < epsilon. Properties: P(T_epsilon) -> 1; |T_epsilon| <= 2^{n(H+epsilon)}; |T_epsilon| >= (1-epsilon)*2^{n(H-epsilon)} for large n.

-\frac{1}{n}\log p(X_1,\ldots,X_n) \xrightarrow{p} H(X)

AEP

|T_\varepsilon^{(n)}| \leq 2^{n(H(X)+\varepsilon)}

Size of typical set

p(x^n) \approx 2^{-nH(X)} \text{ for } x^n \in T_\varepsilon

Probability of typical sequence

Notation

Notation	Meaning
$T_\varepsilon^{(n)}$	Epsilon-typical set of length-n sequences
$H(X)$	Shannon entropy of source distribution

Theorems

Theorem 1: Shannon Source Coding Theorem

For i.i.d. source X with entropy H(X): (i) For any R > H(X), there exists a code with rate R bits/symbol that allows asymptotically lossless compression. (ii) For any R < H(X), any code with rate R bits/symbol will have nonzero asymptotic error probability.

Worked Examples

1
H(X) = (1/2)log2(2) + 2*(1/4)log2(4) = 0.5 + 1 = 1.5 bits.
$H(X) = 1.5 \text{ bits}$
2
Approx number = 2^{nH} = 2^{150}.
$|T_\varepsilon| \approx 2^{100 \times 1.5} = 2^{150}$

✓ Answer

Approximately 2^{150} typical sequences, vs 3^{100} ≈ 2^{158} total sequences.

Practice Problems

Mediumapplication

A binary source has P(X=0)=0.8, P(X=1)=0.2. What is the minimum rate (bits/symbol) for lossless compression?

Common Mistakes

Common Mistake

Thinking typical sequences are the most probable sequences.

Typical sequences are not necessarily the most probable ones -- they are the ones whose probability is close to 2^{-nH}. The most probable sequence (e.g., all 0s for a biased coin) is atypical for large n.

Quiz

The AEP says that as n -> inf, the typical set has probability approaching:

01/212^{nH}

Historical Background

The AEP was implicit in Shannon's 1948 work but was explicitly formalized later. It provides the theoretical foundation for all of source coding theory. McMillan (1953) proved the general form. Breiman (1957) extended it. The AEP connects probability theory (law of large numbers) to information theory (source coding theorem).

1948
Shannon implicitly uses typicality arguments in source coding theorem
Claude Shannon
1953
McMillan formalizes the AEP for stationary ergodic sources
Brockway McMillan

Summary

AEP: -(1/n)log p(X^n) -> H(X) in probability (law of large numbers for information).
Typical set: sequences with probability ≈ 2^{-nH}. About 2^{nH} of them.
Typical set captures probability -> 1 as n -> inf.
Source coding theorem: minimum rate for lossless compression = H(X) bits/symbol.

References

BookCover, T.M. and Thomas, J.A. Elements of Information Theory. 2nd ed. Wiley, 2006.