Method of types

Short description: Technique in information theory

The method of types is a tool in information theory and large deviation theory to analyze events from the perspective of the empirical distribution. It classifies events as typical when the empirical distribution closely matches the true distribution.

It has been used to prove results in hypothesis testing, channel coding, and it is used to prove Sanov's theorem in the finite support setting.

It was popularized by Imre Csiszár, with the first formal treatment given in the book Information Theory: Coding Theorems for Discrete Memoryless Systems.. Csiszár claimed that the technique was originally motivated by the large deviation bound described in Hoeffding's seminal paper on multinomial hypothesis testing.

Motivating example

Given $n$ samples from $P$, a Bernoulli distribution with probability of success $p$, there are $2^n$ possible outcomes. We can group outcomes by the number of successful events, since every collection of $r$ successes has the same probability, $p^r(1-p{)}^{n-r}$, and there are $(\genfrac{}{}{0ex}{}{n}{r})$ such events. This can be summarized by considering the empirical distribution $P_r=(1-\frac{r}{n},\frac{r}{n})$ and the type class $T(P_r)=\{X^n:\sum _{i=1}^n\mathbf{𝟏}\{X_i=1\}=r\}$. With some analysis, one finds that $$\begin{array}{r}\mathbb{\mathbb{P}}\left[X^n\right]=p^r(1-p{)}^{n-r}\approx 2^{-n[H(P_r)+D(P_r\Vert P)]},\\ \mathbb{\mathbb{P}}[T(P_r)]=(\genfrac{}{}{0ex}{}{n}{r})p^r(1-p{)}^{n-r}\approx 2^{-nD(P_r\Vert P)},\end{array}$$ where $H(P_r),D(P_r\Vert P)$ denote the Shannon entropy and relative entropy. These approximations are most accurate when $n$ is taken to be large. A more accruate bound would be $$(n+1{)}^{-2}{2}^{-nD(P_r\Vert P)}\le \mathbb{\mathbb{P}}[T(P_r)]\le 2^{-nD(P_r\Vert P)}.$$

For example, if we wanted to get a rough estimate of the probability of seeing $r=400$ heads in 1000 tosses of a fair coin, we could compute $$\begin{array}{rl}D(P_r\Vert P)& =0.6\log \frac{0.6}{0.5}+0.4\log \frac{0.4}{0.5}\\ & \approx 0.02905\end{array}$$ which gives us the (loose) approximation $$2^{-1000*0.02905}\approx 1.799*10^{-9},$$ while the true value is $$(\genfrac{}{}{0ex}{}{1000}{400})2^{-1000}\approx 4.6339*10^{-11}.$$ The figure below plots the exact probability and the upper and lower bounds.

The probability that $n$ i.i.d. samples of a Bernoulli(1/2) random variable will have type (2/5, 3/5), along with the method-of-types bounds [log scale].

The method of types generalizes the above example to multivariate distributions.

Mathematical formulation

Let ${𝒳}$ be an alphabet with a finite number of elements. We start with a sequence of i.i.d. random variables following a finite support distribution $Q$, $X^n=(X_1,\dots ,X_n)\sim Q$, where $X_i\in {𝒳}$. For this sequence, let $N(k|X^n)=\sum _{i=1}^n\mathbf{𝟏}\{X_i=k\}$ denote the number of occurrences of the symbol $k$ in the sequence $X^n$.

Denote the empirical distribution of the samples with $P_{X^n}$, so that $P_{X^n}[k]=\frac{N(k|X^n)}{n}$. The sets of sequences having empirical distribution $Q$, are called the type classes $T(Q)=\{X^n\in {{𝒳}}^n:P_{X^n}=Q\}$. To describe the set of all empirical distributions possible from $n$ samples, we use the symbol ${{𝒫}}_n$, which is a subset of the $d-1$ dimensional probability simplex ${𝒫}$.

The method of types is built on top of the following results:

• $|{{𝒫}}_n|\le (n+1{)}^{|{𝒳}|}$

• $Q[X^n]=2^{-n[H(P_{X^n})+D(P_{X^n}\Vert Q)]}$

• $\frac{1}{(n+1{)}^{|{𝒳}|}}{2}^{nH(Q)}\le |T(Q)|\le 2^{nH(Q)}$

• $\frac{1}{(n+1{)}^{|{𝒳}|}}{2}^{-nD(P\Vert Q)}\le Q[T(P)]\le 2^{-nD(P\Vert Q)}$

Here $H(P)$ denotes the Shannon entropy, and $D(P\Vert Q)$ denotes the Kullback–Leibler divergence. The last equation is derived from the previous ones by noticing that every element of $T(P)$ has the same probability when the samples are taken i.i.d.

These bounds are tight in terms of the error exponent, but may give a loose bound in terms of $|{𝒳}|$ and the sub-exponential terms in $n$.

Applications

The method of types is used for hypothesis testing problems, when the underlying distributions have finite support, because it provides a tight bound on the error exponent. It was also used to prove some initial conditional limit theorems, which are special cases of the general class of limit theorems. The bound on the size of a type class can be used to prove tight bounds on the exact value on binomial coefficients. It is also used to prove the principle of maximum entropy.

See also

• Asymptotic equipartition property
• Sanov's theorem