= Entropy bounds for a type class
{title2=$\ln|T_n(q)|=nH_e(q)+O(\ln n)$}
For an attainable <empirical distribution> $q$ on a fixed finite <alphabet> of size $m$,
$$
(n+1)^{-m}e^{nH_e(q)}\leq |T_n(q)|\leq e^{nH_e(q)}.
$$
Thus $\ln|T_n(q)|$ differs from $nH_e(q)$ by at most $m\ln(n+1)$, uniformly over attainable profiles. <Information entropy> is the leading logarithmic count; the polynomial factor matters at short lengths.<The Method of Types by Imre Csiszár>[§II, Lemma II.2, equation (II.4), printed pp. 2506–2507: type-class cardinality bounds]{ref}
The upper bound has a short explanation. Under an <independent and identically distributed> source whose law is $q$ itself, each string in $T_n(q)$ has <probability> $e^{-nH_e(q)}$. Multiplying by the number of such strings cannot give a <probability> above one. A corresponding polynomial lower bound follows from the <multinomial coefficient>; the <Stirling's approximation> gives sharper prefactors when needed.
For the balanced four-symbol class, $H_e(q)=\ln2$, so the upper bound is $e^{4\ln2}=16$, while the exact size is six. <Information entropy> is not an exact count for a short string. On the leading scale it becomes precise: the difference divided by $n$ tends to zero as $n$ grows with the <alphabet> fixed.
Back to article page
