Typical Sets

The small set that holds almost all the probability.

The idea

The typical set collects the sequences of $n$ independent draws whose probability is close to $2^{-nH(X)}$, where $H(X)$ is the source's entropy in bits. By the law of large numbers, almost all of the probability of a long run lands on these sequences.

For a sequence $x^{n} = (x_1, \ldots, x_n)$, call

$-\tfrac{1}{n}\log_{2} p(x^{n})$

its sample entropy: the surprise per symbol, in bits, that this particular sequence delivered. Fix a tolerance $\epsilon > 0$. The typical set is the set of sequences whose sample entropy lies within $\epsilon$ of the true entropy,

$A_{\epsilon}^{(n)} = \Bigl\{ x^{n} : \bigl| -\tfrac{1}{n}\log_{2} p(x^{n}) - H(X) \bigr| \le \epsilon \Bigr\},$

which is the same as requiring $2^{-n(H(X)+\epsilon)} \le p(x^{n}) \le 2^{-n(H(X)-\epsilon)}$. For large $n$ this set carries probability greater than $1 - \epsilon$, yet holds only about $2^{nH(X)}$ of the $|\mathcal{X}|^{n}$ possible sequences.

The condition asks a sequence's probability to be near $2^{-nH(X)}$, not to be large. A sequence can be too probable to be typical: for a biased source the single most likely sequence usually has sample entropy far below $H(X)$, and so lies outside the set.

Ways to work on it

• Walkthrough. Define the typical set via sample entropy, see the equipartition, and derive its size bound.
• Practice. Read off a typical-set size or probability from nH(X).
• Hardest. Show the most probable sequence can be atypical, and bound the typical-set size.

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