Typical Sets and the AEP

Flip a fair coin 1000 times. The single most probable outcome is all heads, tied with every other specific sequence at \(2^{-1000}\). Yet you will never see all heads, and you will always see roughly 500 heads. Both statements are about the same distribution, and reconciling them is the content of the asymptotic equipartition property.

This is not a probability-theory curiosity. It is the reason greedy decoding produces degenerate text while sampling produces fluent text, and the reason a language model's most likely continuation is often not a good continuation.

The property

Let \(X_1, \dots, X_n\) be i.i.d. from \(p\). The AEP says that

The left side is the empirical per-symbol surprisal of the sequence you actually drew. It converges in probability to the entropy. Equivalently, with probability approaching one, the sequence you drew satisfies

The set of sequences satisfying that bound is the typical set \(A_\epsilon^{(n)}\). Three facts define its character:

1. Its total probability exceeds \(1 - \epsilon\) for large \(n\). Almost everything that happens, happens inside it.
2. It contains at most \(2^{n(H+\epsilon)}\) sequences, out of \(|\mathcal{X}|^n\) possible ones. For the biased coin with \(p(\text{heads}) = 0.9\), \(H \approx 0.469\) bits, so the typical set holds about \(2^{469}\) of the \(2^{1000}\) sequences: a fraction of roughly \(2^{-531}\).
3. Every member has approximately the same probability, near \(2^{-nH}\). Hence "equipartition".

The mode is not in the typical set. All-heads has surprisal \(0\) per symbol, not \(H\), so it fails the lower bound. It is the most probable single sequence and simultaneously an atypical one, and there is no contradiction because there is exactly one of it.

Why this is the source coding theorem

Once you have the typical set, compression is bookkeeping. Assign each of the \(\le 2^{n(H+\epsilon)}\) typical sequences an index of \(n(H+\epsilon)\) bits, plus one flag bit; give everything else a raw encoding with its own flag. The expected length per symbol approaches \(H\), and no scheme beats it because you cannot injectively index more than \(2^{nR}\) things with \(nR\) bits. Shannon's 1948 source coding theorem in three lines (Shannon, 1948, A Mathematical Theory of Communication).

The decoding connection

Text generation samples from a learned \(p(x_t \mid x_{<t})\), and the same geometry applies. A human-written continuation is a sample, so it lands in the typical set: its per-token surprisal hovers near the model's conditional entropy. Beam search and greedy decoding hunt for the mode, which lands outside it, in the low-surprisal region where the same phrase repeats forever. That is the mechanism behind neural text degeneration, and it explains why the fix is not a better search.

Locally typical sampling makes the connection operational: at each step, restrict the candidate set to tokens whose surprisal \(-\log p(x_t \mid x_{<t})\) is close in absolute value to the conditional entropy \(H(X_t \mid x_{<t})\), then renormalise (Meister et al., 2023, Locally Typical Sampling, TACL 11:102-121). Unlike top-\(k\) and nucleus sampling, which truncate the tail, typical sampling also excludes tokens that are too probable, and it reduces degenerate repetition on summarisation and story generation while staying competitive on quality.

When it breaks

The AEP as stated needs i.i.d. samples; language is not i.i.d. The generalisation to stationary ergodic processes is the Shannon-McMillan-Breiman theorem, which gives almost-sure convergence to the entropy rate, and language is arguably not stationary either. The practical consequence is that "typical" must be evaluated locally, per step, against the model's current conditional entropy, which is exactly what locally typical sampling does and what a global surprisal threshold cannot do.

Second, typicality is a statement about the model's distribution, not about quality. If the model is badly calibrated, its typical set is the typical set of the wrong distribution, and sampling faithfully from it reproduces the model's errors faithfully too. See calibration of language models and entropy and surprise.