The Theorem

A classical source emits letters from a finite alphabet $\mathcal{A}$ , one at a time and independently, each use giving the letter $x$ with the same probability $p(x)$ . The numbers $p(x)$ are nonnegative and sum to one: $p$ is a probability distribution on $\mathcal{A}$ . After $n$ uses the source has emitted a sequence $x = (x_1, \dots, x_n)$ , which occurs with probability $p(x) = p(x_1)\, p(x_2) \cdots p(x_n).$ (1)

There are $|\mathcal{A}|^n$ sequences of length $n$ , and the question is how few of them hold nearly all the probability when $n$ is large. The theorem of typical sequences answers it with the sequences whose probability is close to $e^{-nH}$ , where $H$ is the Shannon entropy of the source.

Entropy and Typical Sequences

The Shannon entropy $H(p)$ of a probability distribution $p$ on a finite alphabet $\mathcal{A}$ is the real number $H(p) = -\sum_{x \in \mathcal{A}} p(x) \log p(x),$ (2)^✦ with the natural logarithm, so that $H(p)$ is measured in nats. We write $H$ for $H(p)$ when the distribution is fixed.

For a length $n$ and a number $\varepsilon$ , the set $T(n,\varepsilon)$ of $\varepsilon$ -typical sequences of the source is the set of sequences $x$ of $n$ letters whose probability (1) satisfies $e^{-n(H+\varepsilon)} \le p(x) \le e^{-n(H-\varepsilon)}.$ (3)^✦ Its number of elements is written $|T(n,\varepsilon)|$ .

The Claim

Theorem 1. Let $p$ be a probability distribution on a finite alphabet, with Shannon entropy $H$ , and let $\delta > 0$ .

For every $\varepsilon > 0$ and all sufficiently large $n$ , the $\varepsilon$ -typical sequences of length $n$ carry probability at least $1 - \delta$ : $\sum_{x \in T(n,\varepsilon)} p(x) \ge 1 - \delta.$ (4)^✦
For every $\varepsilon > 0$ and all sufficiently large $n$ , the number of $\varepsilon$ -typical sequences of length $n$ satisfies $(1 - \delta)\, e^{n(H-\varepsilon)} \le |T(n,\varepsilon)| \le e^{n(H+\varepsilon)}.$ (5)^✦
For every number $R < H$ and all sufficiently large $n$ , every set $S$ of at most $e^{nR}$ sequences of length $n$ carries probability at most $\delta$ : $\sum_{x \in S} p(x) \le \delta.$ (6)^✦

What Is Checked

The claim is stated over the Shannon entropy (2) and the set of typical sequences (3), for every probability distribution on every finite alphabet, the probability of a sequence being the product (1).

About the typical set the library proves the probability bound (4) and the bounds (5) on its size, and about any set of at most $e^{nR}$ sequences with $R < H$ the bound (6).