Method of types

The method of types is a set of counting and probability tools for sequences over a finite alphabet. It is foundational in information theory and large deviations: it turns questions about probabilities of empirical frequencies into entropy and divergence calculations.

It relies on the entropy–counting relationship in entropy-multinomial-coefficients .

Types and type classes

Let $\mathcal{A}$ be a finite alphabet with $|\mathcal{A}|=m$, and let $x^n=(x_1,\dots,x_n)\in\mathcal{A}^n$.

• The type (empirical distribution) of $x^n$ is the probability mass function $P_{x^n}$ on $\mathcal{A}$ defined by

  $$P_{x^n}(a)=\frac{1}{n}\,\#\{i: x_i=a\}.$$

• For a type $P$ with denominator $n$ (i.e., all $nP(a)$ are integers), the type class is

  $$T(P)=\{x^n\in\mathcal{A}^n: P_{x^n}=P\}.$$

Counting: size of a type class

Write $n_a = nP(a)$ for each $a\in\mathcal{A}$. Then

a multinomial coefficient.

Let

(natural-log entropy). Then the type class size satisfies the standard bounds

In particular, $\log |T(P)| = nH(P) + O(\log n)$.

Counting: number of possible types

The number of distinct types on $\mathcal{A}$ with denominator $n$ is at most

because each $P(a)$ must be in $\{0,1/n,2/n,\dots,1\}$.

Probability of a type class under an i.i.d. law

Let $Q$ be a distribution on $\mathcal{A}$, and let $X^n\sim Q^{\otimes n}$ be i.i.d. draws.

For any fixed type $P$ with denominator $n$, every sequence $x^n\in T(P)$ has the same probability:

Therefore,

Introduce the (natural-log) Kullback–Leibler divergence

Using $|T(P)|\approx e^{nH(P)}$ gives the characteristic exponential rate

(up to polynomial factors). A standard bound pair is

Why this is useful

• Converts empirical-frequency events into entropy/divergence exponents.
• Provides finite-$n$ (non-asymptotic) bounds with only polynomial slack.
• Serves as a discrete, combinatorial route to large deviation principles (e.g., the intuition behind Sanov-type results).