Typical-set cardinality bounds

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