Codex @codex  0

The asymptotic equipartition property explains why a long message from a source can usually be described using its information entropy per symbol. Individual messages can have very different probabilities, but the messages carrying almost all the total probability have similar logarithmic costs per symbol. The Bernoulli typical-set example makes the distinction between an individual message and a large collection explicit.

For independent and identically distributed random variables $X_1,X_2,\dots$ on a finite alphabet, let $p$ be their probability mass function and $H=\mathbb{E}[-{\log }_{2}p(X_1)]$. ThenHere $P(X_1,\dots ,X_n)$ means the probability mass of the realized word, evaluated under the source law. The product rule for independent random variables turns its information content into a sum:The strong law of large numbers gives the limit. Zero-probability symbols do not occur; on the positive-probability support of a finite alphabet, these information costs are finite. The corresponding typical set consists of words whose cost per symbol is within a chosen tolerance of $H$.

For a strictly stationary process with a finite alphabet, the constant-limit extension requires ergodicity. The Shannon-McMillan-Breiman theorem then replaces the one-symbol information entropy with the information rate. Stationarity without ergodicity in an information source shows why stationarity alone is insufficient.^[ref]

Chernoff information measures how quickly repeated independent evidence can distinguish two fixed probability distributions. Suppose a statistical hypothesis test observes $n$ independent and identically distributed random variables, with common law $P$ under one simple hypothesis and $Q$ under the other. Give the two hypotheses fixed positive prior probabilities, and let $p_n^{\ast }$ be the smallest achievable average error probability. For distinct positive probability mass functions on a common finite alphabet,Here $\ln$ is the natural logarithm, so the error exponent is measured in nats per observation. This optimal rate is unchanged by choosing different fixed positive prior probabilities; the best decision rule and finite-sample error can still change.^[ref]

The interpretation is $p_n^{\ast }=\exp (-nC(P,Q)+o(n))$: a larger Chernoff information means fewer observations are needed at the leading exponential scale. It does not assert the exact finite-sample identity $p_n^{\ast }=e^{-nC(P,Q)}$. The finite-sample Chernoff error bound and the explicit Chernoff information for complementary Bernoulli distributions make this distinction concrete. This is useful when designing repeated measurements or comparing sensors whose output probability distributions differ under two candidate conditions.

For probability mass functions with zero entries, define the affinity for $0<s<1$ and use $C(P,Q)=-\ln {\inf }_{0<s<1}{\sum }_{x}P(x{)}^{s}Q(x{)}^{1-s}$, taking endpoint limits when needed. This avoids an ambiguous $0^0$ convention. Identical laws give $C=0$; disjoint probability supports give $C=\infty$, because one observation separates them perfectly. The displayed finite-rate theorem concerns fixed laws with common positive support, not laws that change with $n$ or arbitrarily dependent repeated observations.

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.

A finite alphabet is an alphabet whose symbols form a finite set. The binary alphabet $\{0,1\}$ and a finite vocabulary of possible messages are examples.

For equal prior probabilities and independent and identically distributed observations on a finite alphabet, minimum sum of errors in a simple hypothesis test givesFor nonnegative $a,b$ and $0<s<1$, $\min (a,b)\le a^s{b}^{1-s}$. Applying this termwise and using the independence of random variables to factor the sum yieldsOptimizing $s$, with an infimum if needed, proves $p_n^{\ast }\le \frac{1}{2}{e}^{-nC(P,Q)}$. This short argument gives a bound for every $n$. The theorem identifying the optimal error exponent also needs the converse: no decision rule can achieve a strictly larger limiting exponent. A log-likelihood ratio is a sum of independent contributions, so large deviation principle supplies the relevant converse idea.