The method of types replaces sums over sequences by sums over empirical distributions. It is the finite-alphabet combinatorial form of large deviations.
Types and type classes
Definition. For \(x^n\in\mathcal X^n\), its type \(\widehat P_{x^n}\) is the empirical distribution \[ \widehat P_{x^n}(a)=\frac1n\sum_{i=1}^n\mathbf 1\{x_i=a\}. \] The type class \(T_Q\) is the set of strings having type \(Q\).
Counting theorem
Theorem. For a type \(Q\) on alphabet \(\mathcal X\), \[ \frac{\exp(nH(Q))}{(n+1)^{|\mathcal X|}}\le |T_Q|\le \exp(nH(Q)). \] If \(X^n\sim P^n\), then every \(x^n\in T_Q\) has probability \(\exp[-n(H(Q)+D(Q\|P))]\).
Proof by multinomial coefficients
Proof. The size of \(T_Q\) is \(n!/\prod_a(nQ(a))!\). Stirling bounds give the exponential term \(\exp(nH(Q))\) with only polynomial loss. The probability identity follows by writing \(\prod_a P(a)^{nQ(a)}\) and expanding \(H(Q)+D(Q\|P)=-\sum_aQ(a)\log P(a)\).
Why types matter
Remark. Type bounds explain why KL divergence appears in statistics: the number of strings with empirical law \(Q\) is about \(e^{nH(Q)}\), while each has probability about \(e^{-n(H(Q)+D(Q\|P))}\). The entropy terms cancel, leaving \(e^{-nD(Q\|P)}\).
Types and type classes
Definition. The type of \(x^n\in\mathcal X^n\) is its empirical distribution \[ \widehat P_{x^n}(a)=\frac1n\sum_{i=1}^n\mathbf1(x_i=a). \] The type class \(T_Q\) contains all sequences of type \(Q\).
Number of types
Proposition. If \(|\mathcal X|=m\), then the number of \(n\)-types is at most \[ (n+1)^m. \]
Proof. Each count \(nQ(a)\) is an integer between \(0\) and \(n\), giving at most \(n+1\) choices per symbol. The sum constraint only reduces the count.
Size of a type class
Theorem. For every \(n\)-type \(Q\), \[ \frac{1}{(n+1)^m}e^{nH(Q)} \le|T_Q|\le e^{nH(Q)}. \]
Proof. Under the product law \(Q^n\), every sequence in \(T_Q\) has probability \[ \prod_aQ(a)^{nQ(a)}=e^{-nH(Q)}. \] Since \(Q^n(T_Q)\le1\), the upper bound follows. The type classes partition \(\mathcal X^n\) into at most \((n+1)^m\) classes. Under \(Q^n\), \(T_Q\) has maximal probability among types up to the standard type-likelihood argument, so its probability is at least the reciprocal of the number of types, giving the lower bound.
Probability of a type
Theorem. If \(X^n\sim P^n\), then \[ \frac1{(n+1)^m}e^{-nD(Q\|P)} \le P^n(T_Q)\le e^{-nD(Q\|P)}. \]
Proof. Every \(x^n\in T_Q\) has \[ P^n(x^n)= \prod_aP(a)^{nQ(a)} =e^{-n\{H(Q)+D(Q\|P)\}}. \] Multiply by the type-class cardinality bounds.
Conditional types
Definition. Given an input sequence \(x^n\) of type \(P_X\), a conditional type \(V(y\mid x)\) records output frequencies within positions carrying each \(x\). The joint type is \(P_X(x)V(y\mid x)\).
Theorem. The conditional type class satisfies \[ (n+1)^{-|\mathcal X||\mathcal Y|} e^{nH(V\mid P_X)} \le|T_V(x^n)| \le e^{nH(V\mid P_X)}. \] Under memoryless channel \(W\), \[ W^n\{T_V(x^n)\mid x^n\} \doteq e^{-nD(V\|W\mid P_X)}. \]
Proof outline. Partition positions by input symbol and apply ordinary type-class bounds within each block. Multiplying cardinalities adds conditional entropies. Channel likelihood of each conditional-type sequence has exponent \(-H(V\mid P_X)-D(V\|W\mid P_X)\); multiply by class size.
Binary example
Example. For \(X_i\sim\operatorname{Bernoulli}(p)\), the event \(\overline X_n=q\) is a type class and \[ P(\overline X_n=q)\doteq e^{-nD\{\operatorname{Bern}(q)\| \operatorname{Bern}(p)\}}. \] The binomial coefficient contributes \(e^{nh_2(q)}\); the probability of each sequence contributes \(p^{nq}(1-p)^{n(1-q)}\).
Polynomial factors versus exponential rates
The notation \(a_n\doteq e^{-nI}\) discards factors with \(\log a_n+nI=o(n)\). Type theory is powerful because the number of types is polynomial, so a union over types does not change the dominant exponential rate. Polynomial factors do matter for exact and second-order asymptotics.
Typicality from types
Proposition. For every closed set of distributions \(F\) not containing \(P\), \[ P\{\widehat P_n\in F\} \le(n+1)^m \exp\{-n\inf_{Q\in F}D(Q\|P)\}. \]
Proof. Sum the upper type-probability bound over at most \((n+1)^m\) types in \(F\), and bound each exponent by the infimum.
This finite-sample inequality contains the upper half of Sanov's theorem for finite alphabets.