= Probability of a type class
{title2=$\mathbb P_p(T_n(q))=|T_n(q)|e^{-n[H_e(q)+D_e(q\Vert p)]}$}
For a string of <empirical distribution> $q$, <independence> gives
$$
\mathbb P_p(x^n)=\prod_a p(a)^{nq(a)}
=e^{-n[H_e(q)+D_e(q\Vert p)]}.
$$
Multiplying this by the <size of a type class> gives its exact <probability>. The <entropy bounds for a type class> then imply
$$
(n+1)^{-m}e^{-nD_e(q\Vert p)}\leq
\mathbb P_p(T_n(q))\leq e^{-nD_e(q\Vert p)}.
$$
These bounds apply to one attainable <empirical distribution>, not automatically to a tail event containing many classes.<The Method of Types by Imre Csiszár>[§II, equation (II.1) and Lemma II.2, equation (II.5), printed pp. 2506–2507]{ref} If $p(a)=0$ but $q(a)>0$, every string in that class is impossible and $D_e(q\Vert p)=+\infty$.
As an exact example, take an <independent and identically distributed> binary source with $p(1)=1/4$. Each balanced four-symbol string has <probability> $(1/4)^2(3/4)^2=9/256$. There are six such strings, so
$$
\boxed{\mathbb P_p(T_4(1/2,1/2))=\frac{54}{256}=0.2109375.}
$$
The <relative entropy> is $D_e((1/2,1/2)\Vert(3/4,1/4))=\tfrac12\ln(4/3)$. The exponential upper bound is $e^{-4D_e}=9/16=0.5625$, visibly larger than the exact <probability>. It captures the cost of an atypical frequency without supplying the exact finite-length prefactor.
For $n=40$, the exact <probability> of twenty ones is
$$
\binom{40}{20}(1/4)^{20}(3/4)^{20}\approx0.000397577,
$$
while the exponential upper bound is approximately $0.00317121$. At the source frequency $q(1)=1/4$, <relative entropy> is zero and the upper bound is one; the exact <probability> of ten ones is only about $0.144364$. A likely neighborhood of frequencies need not give a large <probability> to a single exact profile.
\Image[/type-class-probability-and-divergence.png]
{title=Relative entropy controls the rarity of an empirical frequency}
{description=Exact <probabilities> from the <binomial distribution> for each possible number of ones in forty <independent and identically distributed> trials with $p(1)=1/4$, compared with the exponential <relative entropy> upper bound. The curves are calculated from a stipulated model, not observed data; the vertical scale is logarithmic.}
The striking cancellation is that there are about $e^{nH_e(q)}$ strings in a class, but each costs about $e^{-n[H_e(q)+D_e(q\Vert p)]}$. The <information entropy> terms cancel, leaving <relative entropy> as the rarity exponent. Summing over polynomially many classes preserves that leading exponential scale. This is the elementary counting mechanism behind finite-alphabet versions of <Sanov theorem> and many <error exponents in hypothesis testing>.
Back to article page
