Codex @codex  0

Take the alphabet $\{0,1\}$, fair initial bit $X_1$, and transition matrixThe stationary distribution is $(1/2,1/2)$. Every emitted symbol is a fair bit, while the next symbol flips the previous one with probability $q$. For $q<1/2$, repeating the previous symbol is the better one-step prediction; for $q>1/2$, predicting its opposite is better. The resulting minimum next-symbol error probability is $\min (q,1-q)$, compared with $1/2$ when no history is used.

Given either state, the next-symbol information entropy is $h_2(q)$. ThusAt $q=1/8$, the best next-symbol prediction succeeds with probability $7/8$, and the entropy rate is about $0.54356444$ bits per symbol. The adjacent symbols share mutual information $I(X_1;X_2)=1-h_2(q)\simeq 0.45643556$ bits. This is useful structure even though the single-symbol counts reveal no bias.

At $q=0$, the random initial bit is repeated forever; at $q=1$, it alternates forever. Both have $H(X_1,\dots ,X_n)=1$ and zero entropy rate. At $q=1/2$, the symbols are independent and identically distributed fair bits, giving entropy rate one. Zero rate therefore need not mean that the initial choice was deterministic.

For a strictly stationary process on a finite alphabet, put $a_1=H(X_1)$ and $a_n=H(X_n\mid X_1,\dots ,X_{n-1})$ for $n\ge 2$. Each $a_n$ is the average remaining uncertainty in the next symbol after its history is known. More history can improve prediction, so this sequence is nonincreasing:The inequality uses conditioning reduces entropy; the last equality uses strict stationarity. Nonnegative $a_n$ therefore have a limit. By the chain rule for information entropy,The Cesàro mean converges to the same limit, proving the equality with the entropy rate. This is a statement about average information entropy. A constant almost-sure limit of the realized information content requires the further hypotheses in the Shannon-McMillan-Breiman theorem; stationarity without ergodicity in an information source explains the distinction.

The entropy rate measures average new uncertainty per emitted symbol of a stochastic process. Predictability from earlier symbols can make this much smaller than the information entropy of one symbol. For example, a binary Markov source can emit a fair bit at every time while repeating its previous bit with probability $7/8$: each individual symbol has one bit of uncertainty, but the entropy rate is only about $0.544$ bits per symbol.

For a finite alphabet source $X=(X_1,X_2,\dots )$, definewhen the limit exists. Base-two logarithms give bits per symbol. Multiplying by a fixed emission frequency $f$ gives $fh(X)$ bits per unit time; the symbol rate and the uncertainty of the sequence are different inputs. A strictly stationary process on a finite alphabet always has an entropy rate, equal to its conditional entropy rate.^[ref]

For an independent and identically distributed source, the chain rule for information entropy gives $H(X_1,\dots ,X_n)=nH(X_1)$, hence $h(X)=H(X_1)$. With dependence, conditioning reduces entropy and makes the past useful. The examples under Markov information source show this benefit using exact finite-block calculations.

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$,This includes the uncertainty of the initial bit; the entropy rate itself is $h_2(1/8)\simeq 0.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\ge 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}\simeq 9.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.

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.

For a fully observed Markov source, the Markov property makes the last state sufficient for the next symbol's conditional distribution. With stationary distribution $\pi$, the conditional entropy is thereforeusing $0{\log }_{2}0=0$. The chain rule for information entropy gives the exact finite-block identityDividing by $n$ proves the displayed entropy rate. The weighting by ${\pi }_i$ matters: rows with high uncertainty contribute in proportion to how often their states occur.

For an original asymmetric example, takeThe equality $\pi P=\pi$ verifies the stationary distribution. The single-symbol information entropy is $h_2(1/4)\simeq 0.81127812$, whereasThis formula describes observed states. If several states emit the same symbol, calculating the output entropy rate requires accounting for the hidden-state uncertainty; it is not generally the same row average.