Asymptotic Equipartition Property

Typical sequences, entropy concentration, and the 2^nH count.

The idea

Asymptotic equipartition property. Let $X_1, X_2, \ldots$ be independent draws from one distribution with entropy $H(X)$ bits. Then, with probability approaching $1$ as $n$ grows,

$-\frac{1}{n}\log_{2}\mathbb{P}(X_1, \ldots, X_n) \;\approx\; H(X).$

This is the law of large numbers applied to log-probabilities. Independence makes the probability of the whole sequence a product, so its negative logarithm is a sum of per-symbol terms $-\log_{2}\mathbb{P}(X_i)$. Those terms are independent, identically distributed, and have mean exactly $H(X)$ — that is the definition of entropy — so dividing by $n$ gives an average, and the average settles on the mean.

The name records the consequence. A long sequence we actually observe has probability close to $2^{-nH(X)}$, and so does almost every other sequence we might have observed instead: they are nearly equally likely, which is the equipartition. Probabilities of that size sum to about $1$ only if there are about $2^{nH(X)}$ of them, so roughly $2^{nH(X)}$ typical sequences carry almost all the probability, and the remaining sequences, however many, carry almost none.

Ways to work on it

• Walkthrough. Entropy, the concentration of log-probability, and the typical-set size.
• Practice. Find the typical-set exponent nH for a given source and block length.
• Hardest. Compute a source entropy and compare its typical set to the full space.

Not sure where to start? Take the ten-question placement test.