= Entropy rate and coding length
Consider a <binary Markov source> with fair initial <bit> and flip <probability> $q=1/8$. Its exact $n$-symbol <information entropy> is $H_n=1+(n-1)h_2(1/8)$. At $n=16$,
$$
H_{16}\simeq9.15346665\ \text{bits},\qquad H_{16}/16\simeq0.57209167\ \text{bits per symbol}.
$$
This includes the uncertainty of the initial <bit>; the <entropy rate> itself is $h_2(1/8)\simeq0.54356444$ <bits> per symbol. The finite-block difference is $(1-h_2(1/8))/n$.
For any finite block distribution, the <entropy lower bound for prefix codes> gives <expected codeword length> $L_n\geq H_n$, while <Shannon coding> achieves $L_n<H_n+1$. These bounds apply to each block as one source symbol, without requiring consecutive blocks to be independent. Here <Huffman coding> on all $2^{16}$ possible 16-symbol words gives the independently calculated value $L_{16}\simeq9.19511361$ <bits> per block, or $0.57469460$ <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 $L_n/n$ towards the <entropy rate> when an optimal code is used.
\Image[/entropy-rate-block-cost-and-flip-probability.png]
{title=Fair marginal bits can have a lower entropy rate, with a finite-block initial cost}
{description=The left panel shows the exact <binary entropy> $h_2(q)$ for the symmetric <binary Markov source>; each individual symbol still has one <bit> of <information entropy>. Both near-persistence $q\approx0$ and near-alternation $q\approx1$ make the next symbol predictable. The right panel uses $q=1/8$ and plots $H_n/n=h_2(q)+(1-h_2(q))/n$, rather than literal fractional <codeword lengths>. The <Huffman coding> point is the exact expected length over all 16-symbol words.}
An <entropy rate> below one does not allow every word to fit into a shorter fixed binary word with zero error. For $0<q<1$, all $2^n$ binary words are possible, so an injective fixed-length code needs at least $n$ <bits>. Compression instead exploits variable <codeword lengths>, or the vanishing-error convention in <reliable source encoding at a rate>. These are different guarantees.
Back to article page
