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]

Take an IID random variable source of bits with $P(X_j=1)=1/4$. Its binary entropy isA word of length $n$ containing $k$ ones has probability $(1/4{)}^k(3/4{)}^{n-k}$. Its information content per symbol isThus weakly typical sequences for this biased source have $k/n$ near $1/4$. With tolerance $\epsilon =0.1$ bits per symbol, the exact condition isFor $n=40$, this includes exactly $k=8,9,10,11,12$. There are $\left(\genfrac{}{}{0ex}{}{40}{k}\right)$ words with each count: a type class with that many possible orderings. Summing the counts and their probability masses givesThese are fewer than one percent of the $2^{40}$ possible words, yet they carry nearly 64 percent of the probability. The most likely individual word is all zeros, with probability $(3/4{)}^{40}\approx 1.006\times 10^{-5}$; it is outside this typical set. No contradiction is involved: the type classes near ten ones each contain many more individual words.

In his 1998 retrospective, Imre Csiszár describes the method of types as a 1970s refinement of the typical set approach, with older counting ingredients. He credits his research group with turning those ingredients into a general tool, while explicitly declining to give a complete discovery history.^[ref] The useful shift is from an approximately typical collection to exact frequency classes: the latter retain enough structure to study how fast error probabilities decay.

For a finite-alphabet IID source and fixed $0<\epsilon <1$, the smallest set of length-$n$ strings carrying probability at least $1-\epsilon$ has size $2^{n(H(U)+o(1))}$. The typical set bounds give the upper estimate. For the lower estimate, any such set intersects the typical set in probability bounded away from zero, while each typical string has probability at most $2^{-n(H(U)-\delta )}$.

// Target: probability-and-statistics.bigb

For finite-alphabet independent and identically distributed random variables, fixed $0\le ϵ<1$ and $\delta >0$, every epsilon-sufficient set $S_n$ of length-$n$ words satisfies $|S_n|\ge (1-ϵ)2^{n(H-\delta )}/2$ for sufficiently large $n$. Intersect $S_n$ with a typical set whose excluded mass is at most $(1-ϵ)/2$. The intersection retains that much probability and each word has probability at most $2^{-n(H-\delta )}$.

Use base-two logarithms and put $H=H(U_1)=-{\sum }_i{p}_i{\log }_2{p}_i$, with $0{\log }_{2}0=0$. Zero-probability letters can be omitted. The random variables $I_j=-{\log }_2{p}_{U_j}$ are self-information values, are IID, and have finite mean $H$ because the alphabet is finite. Independence givesFor an arbitrary $\delta >0$, define the typical setThe weak law of large numbers implies $P(T_{n,\delta })\to 1$. Every string in this set satisfiesThis 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 $|T_{n,\delta }|\le 2^{n(H+\delta )}$. For sufficiently large $n$, its probability is at least $1-\epsilon$, so it is an admissible set in the definition of $M(n,\epsilon )$. HenceFor the lower bound, let $A$ be any admissible set and write ${\eta }_n=P(T_{n,\delta }^c)\to 0$. ThenEach member of this intersection has probability at most $2^{-n(H-\delta )}$. Therefore, for all sufficiently large $n$,This applies in particular to a minimum-size admissible set, giving a liminf at least $H-\delta$. Letting $\delta \downarrow 0$ proves both existence and the value of the minimal high-probability source-set exponent:For a deterministic source, $H=0$ and $M(n,\epsilon )=1$, consistent with the formula.

For coding, label the strings in an admissible set with distinct binary indices of length $\lceil {\log }_{2}M(n,\epsilon )\rceil$. A decoder reconstructs those strings exactly and may fail outside the set. Thus asymptotically $H$ bits per source symbol describe any fixed fraction $1-\epsilon$ of the probability mass. More strongly, every rate $R>H$ permits block codes with error tending to zero: choose $\delta <R-H$, encode the typical strings individually and reserve one index for all other strings. The required number of indices is at most $2^{n(H+\delta )}+1\le 2^{nR}$ for large $n$.

Conversely, a block encoder with at most $2^{nR}$ outputs can reconstruct at most that many distinct input strings correctly. If $R<H$, choose $0<\delta <H-R$. Its success probability is at mostThis 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 ${\log }_2|\{i:p_i>0\}|$.

Use base-two logarithms throughout, so classical rates are measured in bits and quantum compression rates in qubits. A memoryless classical information source is a sequence $U_1,U_2,\dots$ of independent and identically distributed random variables on a finite alphabet $\mathcal{U}$, with fixed probability mass function $p$. A length-$n$ word has probability $p(u^n)={\prod }_{j=1}^{n}p(u_j)$, and the one-symbol Shannon entropy is $H(U)=-{\sum }_{u}p(u){\log }_{2}p(u)$, with $0{\log }_{2}0=0$.

For $\epsilon >0$, the typical set isThis is weak typicality: it constrains the normalized self-information, not each empirical symbol count separately.

The typical sequence theorem gives the following three facts for fixed $\epsilon >0$. The probability $P(U^n\in T_{\epsilon }^{(n)})$ tends to one; each word in the set has probability between $2^{-n(H(U)+\epsilon )}$ and $2^{-n(H(U)-\epsilon )}$; and, once the set has probability at least $1-\delta$,The concentration assertion follows from the weak law of large numbers applied to the iid information variables $-{\log }_{2}p(U_j)$, whose finite-alphabet mean is $H(U)$. The probability bounds are the definition of typicality exponentiated. Summing the lower bound over the typical words and using total probability at most one proves the cardinality upper bound; summing the upper bound and using total typical probability at least $1-\delta$ proves the lower bound.

Fix $R>H(U)$ and choose $0<\epsilon <R-H(U)$. Enumerate all words in $T_{\epsilon }^{(n)}$ and assign a distinct fixed-length binary index to each. Reserve one more index as a failure symbol for every atypical input. For all sufficiently large $n$,so these indices can be transmitted using $\lceil nR\rceil$ bits. The decoder inverts the typical-word enumeration; on the failure index it returns any fixed word. This describes both the compressor and decompressor, and its block error probability obeysIts rate tends to $R$ bits per symbol. Thus every $R>H(U)$ permits reliable fixed-rate compression, with no claim that atypical words are reconstructed correctly.

For the memoryless quantum information source, the average one-use density matrix isIts trace is one and determinant $1/8$, so its two eigenvalues areThe source-coding limit in Schumacher compression is the Von Neumann entropy of this average state: every larger qubit rate allows asymptotically faithful recovery of the emitted states, and a smaller rate cannot do so. Applying that limit giveswhere $h_2(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$ is the binary entropy. The quantum typical subspace of ${\rho }^{\otimes n}$ has dimension about $2^{nS(\rho )}$ and carries asymptotically all source weight, which explains the compression rate. The entropy of the classical emission label is one bit; it is not the quantum rate because the two emitted pure states are nonorthogonal.

Let $Y_i=-{\log }_2{P}_Z(Z_i)$. Since the alphabet is finite, these independent and identically distributed random variables are finite almost surely, have mean $H(Z)$, and have finite variance $v$. AlsoThe weak law of large numbers says that this average converges in probability to $H(Z)$. ThusOne can also state the quantitative Chebyshev inequality bound $\mathrm{Pr}(Z^{(n)}\notin T_{\delta }^n)\le v/(n{\delta }^2)$. If $v=0$, every word of positive probability is in the typical set. This is the finite-alphabet asymptotic equipartition property.

Every word in the typical set has probability at least $2^{-n(H(Z)+\delta )}$. ConsequentlyRearranging proves the upper estimate in the typical-set cardinality bounds:

Fix $0\le ϵ<1$ and $\delta >0$. By the asymptotic equipartition property, all sufficiently large $n$ satisfy $\mathrm{Pr}(Z^{(n)}\notin T_{\delta }^n)\le (1-ϵ)/2$. For any epsilon-sufficient set $S_n$,Each word in this intersection has probability at most $2^{-n(H(Z)-\delta )}$. Hencewhich gives the minimum size of a sufficient set for an IID source:The Chebyshev inequality used above supplies the sufficient quantitative condition $n\ge 2v/[{\delta }^2(1-ϵ)]$. No assumption that $S_n$ itself is a typical set is needed; its intersection with one provides the bound.

Use the weak notion of a typical set. For a word $z^n=(z_1,\dots ,z_n)$ write $P_Z^n(z^n)={\prod }_{i=1}^n{P}_Z(z_i)$. The definition isA weakly typical sequence therefore has probability between $2^{-n(H(Z)+\delta )}$ and $2^{-n(H(Z)-\delta )}$. Words containing zero-probability symbols are excluded. These two bounds and the weak law of large numbers provide the three conclusions below.

Use base-two logarithms. The weakly typical sequence definition isEquivalently, $2^{-n(H(X)+\epsilon )}\le p(x^n)\le 2^{-n(H(X)-\epsilon )}$. By the weak law of large numbers applied to the independent and identically distributed random variables $-{\log }_{2}p(X_j)$, the probability of this typical set tends to one.

This captures the usual probability scale of a long sample, but it need not make every symbol frequency representative. For a fair binary source, every word has probability $2^{-n}$ and $H(X)=1$, so even the all-zero word is weakly typical. The strongly typical sequence definition additionally controls empirical symbol frequencies and excludes this word for small tolerance. Thus weak typicality agrees with the high-probability-set intuition, while allowing individually unrepresentative members.

Every member of the typical set has probability at least $2^{-n(H(X)+\epsilon )}$. Summing these probabilities givessoThe upper bound itself holds at every block length. For sufficiently large $n$, the high-probability property also gives the companion lower boundhence $|T_{\epsilon }^{(n)}|\ge (1-\delta )2^{n(H(X)-\epsilon )}$. Together these are the typical-set cardinality bounds underlying Shannon source coding theorem.

Memorylessness means that the ensemble's average density operator is ${\rho }^{(n)}={\pi }^{\otimes n}$. Its spectral decomposition isThe product eigenvalues giveZero eigenvalues contribute zero to the Von Neumann entropy and are excluded from logarithmic typicality tests.

The quantum typical subspace is the span of eigenvectors whose eigenvalues satisfyIts orthogonal projection $P_{\epsilon }^{(n)}$ selects precisely the classical typical set for the eigenvalue distribution $q$. The typical-set cardinality bounds and the weak law of large numbers therefore givefor any fixed $\delta >0$ and all sufficiently large $n$.

A rate-$R$ block code consists of an encoder $E_n:J^n\to \{1,\dots ,M_n\}$ and decoder $D_n$, with $M_n\le 2^{nR}$; it is reliable when $\mathrm{Pr}[D_n(E_n(U^n))\ne U^n]\to 0$. Choose $\epsilon >0$ with $H(U)+\epsilon <R$. The typical set has probability tending to one and cardinality at most $2^{n(H(U)+\epsilon )}\le 2^{nR}$. Encode its words injectively and map every atypical word to a default codeword. The error probability is at most the atypical probability, so reliable compression exists.

A quantum rate-$R$ code uses a compression channel into a space of dimension at most $2^{nR}$ followed by a decompression channel; reliability means that its entanglement fidelity, and hence its average source-state fidelity, tends to one on ${\pi }^{\otimes n}$. Diagonalize $\pi ={\sum }_{u}p(u)|u⟩⟨u|$. The projector onto eigenvectors labelled by the classical typical set has dimension at most $2^{n(S(\pi )+\epsilon )}$ and expectation in ${\pi }^{\otimes n}$ tending to one. For $R>S(\pi )$ choose $\epsilon$ so this typical subspace fits in $2^{nR}$ dimensions, encode it isometrically, and send the orthogonal complement to a fixed state. The typical-subspace probability and the gentle-measurement estimate make the fidelity tend to one. This is Schumacher compression.

For a memoryless classical information source, the typical set consists of positive-probability words with $|-(1/n){\log }_{2}p(u^n)-H(U)|\le \epsilon$. The weak law of large numbers applied to $-{\log }_{2}p(U_j)$ proves its probability tends to one. Every typical word has probability between $2^{-n(H+\epsilon )}$ and $2^{-n(H-\epsilon )}$. Summing the lower bound gives the displayed cardinality upper bound; if the set has probability at least $1-\delta$, summing the upper bound gives cardinality at least $(1-\delta )2^{n(H-\epsilon )}$.

To compress at any rate $R>H(U)$, choose $0<\epsilon <R-H(U)$, assign one fixed-length binary index to each typical word, and reserve one additional index for all atypical words. At most $\lceil nR\rceil$ bits suffice for all large $n$. Decoding inverts the typical-word indices and makes an arbitrary output for the reserved index. The reconstruction error is at most the probability of the atypical set and tends to zero.

For a typical set of probability at least $1-\delta$,The upper bound sums the lower probability bound for each word; the lower bound sums the upper probability bound and uses the set's total probability. These bounds turn the asymptotic equipartition property into exponential estimates of source-coding dimension.

The count $K_n$ has binomial distribution with mean $n/4$ and variance $3n/16$. The information content per symbol is an affine function of $K_n/n$, so its variance isChebyshev's inequality therefore gives the finite-sample lower boundThe bound is often loose, but it proves that every fixed positive tolerance eventually captures nearly all the probability. Direct summation of the binomial distribution's probability masses gives $P(T_{0.1}^{(640)})\approx 0.999779$. A finite sample does not need to have a nearly full typical set: the 40-symbol example above captures only about $0.639$.