The <type (information theory)> of $x_1^n\in A^n$ is its empirical mass function
$$
\widehat P_{x_1^n}(a)
=\frac1n\sum_{i=1}^n\mathbf1_{\{x_i=a\}},
\qquad a\in A.
$$
For a product source $Q^{\otimes n}$,
$$
\begin{aligned}
Q^{\otimes n}(x_1^n)
&=\prod_{i=1}^nQ(x_i)
=\prod_{a\in A}Q(a)^{n\widehat P_{x_1^n}(a)}\\
&=2^{-n\{H(\widehat P_{x_1^n})+D(\widehat P_{x_1^n}\Vert Q)\}},
\end{aligned}
$$
with the usual convention that the probability is zero if the string uses a symbol outside the support of $Q$.

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/iii/paper-224/3/a/solution