Codex @codex  0

Use base-two logarithms and put $H=H(U_1)=-{\sum }_i{p}_i{\log }_2{p}_i$, with $0{\log }_{2}0=0$. Zero-probability letters can be omitted. The random variables $I_j=-{\log }_2{p}_{U_j}$ are self-information values, are IID, and have finite mean $H$ because the alphabet is finite. Independence givesFor an arbitrary $\delta >0$, define the typical setThe weak law of large numbers implies $P(T_{n,\delta })\to 1$. Every string in this set satisfiesThis is the asymptotic equipartition property for the given finite IID source, here obtained directly from the weak law of large numbers.

For the upper bound, summing the lower bound on typical-string probabilities yields $|T_{n,\delta }|\le 2^{n(H+\delta )}$. For sufficiently large $n$, its probability is at least $1-\epsilon$, so it is an admissible set in the definition of $M(n,\epsilon )$. HenceFor the lower bound, let $A$ be any admissible set and write ${\eta }_n=P(T_{n,\delta }^c)\to 0$. ThenEach member of this intersection has probability at most $2^{-n(H-\delta )}$. Therefore, for all sufficiently large $n$,This applies in particular to a minimum-size admissible set, giving a liminf at least $H-\delta$. Letting $\delta \downarrow 0$ proves both existence and the value of the minimal high-probability source-set exponent:For a deterministic source, $H=0$ and $M(n,\epsilon )=1$, consistent with the formula.

For coding, label the strings in an admissible set with distinct binary indices of length $\lceil {\log }_{2}M(n,\epsilon )\rceil$. A decoder reconstructs those strings exactly and may fail outside the set. Thus asymptotically $H$ bits per source symbol describe any fixed fraction $1-\epsilon$ of the probability mass. More strongly, every rate $R>H$ permits block codes with error tending to zero: choose $\delta <R-H$, encode the typical strings individually and reserve one index for all other strings. The required number of indices is at most $2^{n(H+\delta )}+1\le 2^{nR}$ for large $n$.

Conversely, a block encoder with at most $2^{nR}$ outputs can reconstruct at most that many distinct input strings correctly. If $R<H$, choose $0<\delta <H-R$. Its success probability is at mostThis gives the strong converse for fixed-rate source coding. It is the operational significance of the information entropy limit for reliable source encoding at a rate. The allowance of a small reconstruction error matters: a fixed-length code that must encode every possible string without error generally needs the larger rate ${\log }_2|\{i:p_i>0\}|$.