= Typical sequence theorem
{title2=$\mathbb P(T_\varepsilon^{(n)})\to1,\quad |T_\varepsilon^{(n)}|\leq2^{n(H+\varepsilon)}$}
For a <memoryless classical information source>, the <typical set> consists of positive-probability words with $|-(1/n)\log_2p(u^n)-H(U)|\leq\varepsilon$. The <weak law of large numbers> applied to $-\log_2p(U_j)$ proves its probability tends to one. Every typical word has probability between $2^{-n(H+\varepsilon)}$ and $2^{-n(H-\varepsilon)}$. 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-\varepsilon)}$.
To compress at any rate $R>H(U)$, choose $0<\varepsilon<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.
Back to article page
