Consider a binary Markov source with fair initial bit and flip probability . Its exact -symbol information entropy is . At ,
This includes the uncertainty of the initial bit; the entropy rate itself is bits per symbol. The finite-block difference is .
For any finite block distribution, the entropy lower bound for prefix codes gives expected codeword length , while Shannon coding achieves . These bounds apply to each block as one source symbol, without requiring consecutive blocks to be independent. Here Huffman coding on all possible 16-symbol words gives the independently calculated value bits per block, or bits per symbol. The noninteger value is an expected value; each actual codeword has an integer length. As the block length grows, the prefix code bounds squeeze towards the entropy rate when an optimal code is used.
Figure 1.
Fair marginal bits can have a lower entropy rate, with a finite-block initial cost
. The left panel shows the exact binary entropy for the symmetric binary Markov source; each individual symbol still has one bit of information entropy. Both near-persistence and near-alternation make the next symbol predictable. The right panel uses and plots , rather than literal fractional codeword lengths. The Huffman coding point is the exact expected length over all 16-symbol words. Details.
An entropy rate below one does not allow every word to fit into a shorter fixed binary word with zero error. For , all binary words are possible, so an injective fixed-length code needs at least bits. Compression instead exploits variable codeword lengths, or the vanishing-error convention in reliable source encoding at a rate. These are different guarantees.
Use base-two logarithms and put , with . Zero-probability letters can be omitted. The random variables are self-information values, are IID, and have finite mean because the alphabet is finite. Independence gives
For an arbitrary , define the typical set
The weak law of large numbers implies . Every string in this set satisfies
This 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 . For sufficiently large , its probability is at least , so it is an admissible set in the definition of . Hence
For the lower bound, let be any admissible set and write . Then
Each member of this intersection has probability at most . Therefore, for all sufficiently large ,
This applies in particular to a minimum-size admissible set, giving a liminf at least . Letting proves both existence and the value of the minimal high-probability source-set exponent:
For a deterministic source, and , consistent with the formula.
For coding, label the strings in an admissible set with distinct binary indices of length . A decoder reconstructs those strings exactly and may fail outside the set. Thus asymptotically bits per source symbol describe any fixed fraction of the probability mass. More strongly, every rate permits block codes with error tending to zero: choose , encode the typical strings individually and reserve one index for all other strings. The required number of indices is at most for large .
Conversely, a block encoder with at most outputs can reconstruct at most that many distinct input strings correctly. If , choose . Its success probability is at most
This 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 .
The source is reliably encodable at rate if, for each block length , there are an encoder with at most outputs and a decoder such that the block error probability
tends to zero as .
Its information rate is the limiting information entropy per source symbol,
when this limit exists.