Typical set ($T_{\epsilon }^{(n)}$)

For an IID source, the epsilon-typical set consists of words $u^n$ satisfying $|-(1/n)\log p(u^n)-H(U)|\le \epsilon$. Its probability tends to one, and its cardinality is at most $2^{n(H(U)+\epsilon )}$.

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.

For an IID random variable source with probability mass function $p$, a word $x^n$ is weakly typical when $|-(1/n){\log }_{2}p(x^n)-H(X)|\le \epsilon$. It has probability on the scale $2^{-nH(X)}$. The weak law of large numbers makes the typical set probable, but does not make every word in it representative: for a uniform source every possible word is weakly typical.

For a typical set of probability at least $1-\delta$,The upper bound sums the lower probability bound for each word; the lower bound sums the upper probability bound and uses the set's total probability. These bounds turn the asymptotic equipartition property into exponential estimates of source-coding dimension.

For a finite-alphabet IID source and fixed $0<\epsilon <1$, the smallest set of length-$n$ strings carrying probability at least $1-\epsilon$ has size $2^{n(H(U)+o(1))}$. The typical set bounds give the upper estimate. For the lower estimate, any such set intersects the typical set in probability bounded away from zero, while each typical string has probability at most $2^{-n(H(U)-\delta )}$.

// Target: probability-and-statistics.bigb