Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 224 / 3

The type of $x_1^n\in A^n$ is its empirical mass functionFor a product source $Q^{\otimes n}$,with the usual convention that the probability is zero if the string uses a symbol outside the support of $Q$.

The type class isWe 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 factorRepeated 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}$-probabilityThe lemma therefore givesand hence

Draw $X_1^n$ uniformly from $B$ and let $J$ be uniform on $\{1,\dots ,n\}$ independently. ThenIf $P_i$ denotes the marginal law of $X_i$, this also says $P_B=n^{-1}{\sum }_i{P}_i$. Since $X_1^n$ is uniform on $B$,Subadditivity of information entropy followed by concavity of information entropy givesExponentiating proves $|B|\le 2^{nH(P_B)}$.