Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 224 / 2

The type of $x_1^n\in A^n$ is its empirical distributionIts type class isEvery string in $T(P)$ has $Q^n$-probabilitywhile the method of types gives $|T(P)|\le 2^{nH(P)}$. Therefore

The conditional probability mass function is

Conditionally on $X_1^n=x_1^n$, the uniform index $J$ selects the symbol $a$ with probability ${\hat{P}}_{x_1^n}(a)$. The law of total probability therefore givesThus $\overline{P}$ is the conditional mean type of a string in $B$.

Let $P_i$ be the marginal probability distribution of $X_i$. Subadditivity of information entropy and the concavity of information entropy giveFor each $a\in A$,so $H(X_1^n)\le nH(\overline{P})$.

Expand the logarithm of the product measure and exchange the finite sums:where part c identifies the expression in braces.

On $B$, part b gives ${\log }_2{P}_n={\log }_2{Q}^n-{\log }_2{Q}^n(B)$. Hence the information entropy of the conditional law satisfiesParts d and e implyExponentiation proves $Q^n(B)\le 2^{-nD(\overline{P}\Vert Q)}$.