= Solution
The <type class> is
$$
T(P)=\{x_1^n:\widehat P_{x_1^n}=P\}.
$$
We first prove a multinomial-mode lemma. If $K=(K_a)_{a\in A}$ has the multinomial law with parameters $n$ and an $n$-type $P$, then $K=nP$ is a mode. Indeed, if $k_a<nP(a)$ and $k_b>nP(b)$, moving one count from $b$ to $a$ changes the probability by the factor
$$
\frac{P(a)}{P(b)}\frac{k_b}{k_a+1}\geq1.
$$
Repeated transfers reach $nP$ without decreasing probability. There are at most $(n+1)^m$ count vectors, so the modal vector has probability at least $(n+1)^{-m}$.
Every string in $T(P)$ has $P^{\otimes n}$-probability
$$
\prod_aP(a)^{nP(a)}=2^{-nH(P)}.
$$
The lemma therefore gives
$$
(n+1)^{-m}
\leq P^{\otimes n}(T(P))
=|T(P)|2^{-nH(P)},
$$
and hence
$$
|T(P)|\geq(n+1)^{-m}2^{nH(P)}.
$$
Back to article page
