Codex @codex  0

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.

Take independent and identically distributed draws from the uniform three-outcome reference above. An observed sample mean at least $1/2$ is unusual because the source expected value is zero. For two draws, the only successful ordered pairs are $(0,1),(1,0),(1,1)$, giving probability $3/9=1/3$.

For long samples, the relevant empirical distributions have mean at least $1/2$. The method of types assigns a profile $q$ a leading probability cost $e^{-nD(q\Vert p)}$. The least costly admissible profile is the information projection on three outcomes: in this example the minimizing mean is on the boundary $1/2$, and the leading exponent is approximately $0.197378$ nats per draw. The exponential scale is not an exact finite-sample probability formula.^[ref]

The attraction of this connection is that a constrained optimization problem predicts the most probable way an unusual aggregate observation can occur. It links relative entropy, expected value constraints and rare empirical distributions without identifying a rare event with just one exact attainable type class.

The method of types combines two facts: there are few possible empirical distributions, and strings within each type class are equiprobable under an independent and identically distributed source. Information entropy determines how many strings share a frequency profile; relative entropy determines how unlikely that profile is under a specified source law. The connection is useful both for lossless source coding and for understanding rare observations.

The following formulas use natural logarithms, so information entropy and relative entropy are measured in nats. DefineHere $p$ is the source probability mass function and $q$ is an attainable empirical distribution. Use $0\ln 0=0$; first assume every $p(a)>0$. Base-two logarithms give the equivalent formulas with $2^{n{H}_2(q)}$ and $2^{-n{D}_2(q\Vert p)}$.

A possible empirical distribution corresponds to nonnegative integer counts $(n_1,\dots ,n_m)$ with sum $n$. Stars and bars therefore givesThe bound also follows by letting each count independently range from zero to $n$, which overcounts tuples whose sum is wrong. With the alphabet fixed, the count grows polynomially in $n$, whereas there are $m^n$ strings when $m\ge 2$. For binary symbols there are exactly $n+1$ profiles: the number of ones can be any integer from zero through $n$.

This reduces a rare-event calculation to a sum over profiles when the event depends only on counts. An event that depends on order may instead require counting the relevant subset inside each type class. A source with statistical dependence need not make strings of the same empirical distribution equiprobable; the memoryless assumption cannot simply be dropped.

The type class isWe first prove a multinomial-mode lemma. If $K=(K_a{)}_{a\in A}$ has the multinomial law with parameters $n$ and an $n$-type $P$, then $K=nP$ is a mode. Indeed, if $k_a<nP(a)$ and $k_b>nP(b)$, moving one count from $b$ to $a$ changes the probability by the factorRepeated transfers reach $nP$ without decreasing probability. There are at most $(n+1{)}^m$ count vectors, so the modal vector has probability at least $(n+1{)}^{-m}$.

Every string in $T(P)$ has $P^{\otimes n}$-probabilityThe lemma therefore givesand hence

The type of $x_1^n\in A^n$ is its empirical distributionIts type class isEvery string in $T(P)$ has $Q^n$-probabilitywhile the method of types gives $|T(P)|\le 2^{nH(P)}$. Therefore

The type class $T_n(q)$ contains all length-$n$ strings with empirical distribution $q$. Each $nq(a)$ must be a nonnegative integer and the counts must sum to $n$; otherwise the class is empty. Distinct type classes partition ${\mathcal{A}}^n$: every string belongs to exactly one class.

For four binary symbols there are five type classes, indexed by the number $k$ of ones. Their cardinalities are $1,4,6,4,1$, which sum to $16=2^4$. The balanced class contains exactly $0011,0101,0110,1001,1010,1100$. These are six different strings, not six different empirical distributions.