 Typical sequence theorem

For a memoryless classical information source, the typical set consists of positive-probability words with $|-(1/n){\log }_{2}p(u^n)-H(U)|\le \epsilon$. The weak law of large numbers applied to $-{\log }_{2}p(U_j)$ proves its probability tends to one. Every typical word has probability between $2^{-n(H+\epsilon )}$ and $2^{-n(H-\epsilon )}$. Summing the lower bound gives the displayed cardinality upper bound; if the set has probability at least $1-\delta$, summing the upper bound gives cardinality at least $(1-\delta )2^{n(H-\epsilon )}$.

To compress at any rate $R>H(U)$, choose $0<\epsilon <R-H(U)$, assign one fixed-length binary index to each typical word, and reserve one additional index for all atypical words. At most $\lceil nR\rceil$ bits suffice for all large $n$. Decoding inverts the typical-word indices and makes an arbitrary output for the reserved index. The reconstruction error is at most the probability of the atypical set and tends to zero.