= Minimal high-probability source-set exponent
{title2=$\lim_{n\to\infty}n^{-1}\log_2 M(n,\varepsilon)=H(U)$}
For a finite-alphabet IID source and fixed $0<\varepsilon<1$, the smallest set of length-$n$ strings carrying probability at least $1-\varepsilon$ 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
Back to article page
