Method of types

Summarize Timeline Top Qs Fact Check

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

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

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

Summarize Timeline Top Qs Fact Check

Let ${\displaystyle {\mathcal {X}}}$ 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 ${\displaystyle Q}$, ${\displaystyle X^{n}=(X_{1},\dots ,X_{n})\sim Q}$, where ${\displaystyle X_{i}\in {\mathcal {X}}}$. For this sequence, let ${\displaystyle N(k|X^{n})=\sum _{i=1}^{n}\mathbf {1} \{X_{i}=k\}}$ denote the number of occurrences of the symbol ${\displaystyle k}$ in the sequence ${\displaystyle X^{n}}$.

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

The method of types is built on top of the following results:^[1]

• ${\displaystyle |{\mathcal {P}}_{n}|\leq (n+1)^{|{\mathcal {X}}|}}$

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

• ${\displaystyle {\frac {1}{(n+1)^{|{\mathcal {X}}|}}}2^{nH(Q)}\leq |T(Q)|\leq 2^{nH(Q)}}$

• ${\displaystyle {\frac {1}{(n+1)^{|{\mathcal {X}}|}}}2^{-nD(P\|Q)}\leq Q[T(P)]\leq 2^{-nD(P\|Q)}}$

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

These bounds are tight in terms of the error exponent,^[16] but may give a loose bound in terms of ${\displaystyle |{\mathcal {X}}|}$ and the sub-exponential terms in ${\displaystyle n}$.^[17]

The method of types is used for hypothesis testing problems, when the underlying distributions have finite support^[18][2][19], because it provides a tight bound on the error exponent. It was also used to prove some initial conditional limit theorems^[20], 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^[1]. It is also used to prove the principle of maximum entropy.^[21]

• Asymptotic equipartition property
• Sanov's theorem