Entropy rate ($h(X)={\lim }_{n\to \infty }H(X_1,\dots ,X_n)/n$)

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.

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.

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.

In A Mathematical Theory of Communication by Claude Shannon, Claude Shannon compares block uncertainty per symbol, denoted $G_N$, with conditional uncertainty given the preceding symbols, denoted $F_N$. Theorems 5 and 6 connect both decreasing approximations to the source's limiting uncertainty. He uses symbol statistics at increasing block lengths to expose structure missed by single-letter counts.^[ref] The fair marginal bits of the binary Markov source provide a small exact example of that distinction.

A source is reliably encodable at rate $r$ if there are block encoders with at most $2^{nr}$ outputs and corresponding decoders whose probability of reconstructing the first $n$ source symbols incorrectly tends to zero as $n\to \infty$.

For a finite-alphabet IID source of entropy $H$, fixed-length block codes of rate $R<H$ have reconstruction success probability tending to zero. At most $2^{nR}$ strings can be correctly reconstructed. Their typical probability is at most $2^{nR}{2}^{-n(H-\delta )}$, and the atypical probability tends to zero; choose $0<\delta <H-R$.

// Target: algebra.bigb

For a source $(X_n)$ and fixed positive integer $N$, form the block source $Y_i=(X_{(i-1)N+1},\dots ,X_{iN})$. Whenever the original information rate $h$ exists, the blocked source has information rate $Nh$, because