The <type (information theory)> of $x_1^n\in A^n$ is its <empirical distribution>
$$
\widehat P_{x_1^n}(a)=\frac1n\sum_{i=1}^n\mathbf1_{\{x_i=a\}},
\qquad a\in A.
$$
Its <type class> is
$$
T(P)=\{y_1^n\in A^n:\widehat P_{y_1^n}=P\}.
$$
Every string in $T(P)$ has $Q^n$-probability
$$
\prod_{a\in A}Q(a)^{nP(a)}
=2^{-n\{H(P)+D(P\Vert Q)\}},
$$
while the <method of types> gives $|T(P)|\leq2^{nH(P)}$. Therefore
$$
Q^n(T(P))\leq2^{-nD(P\Vert Q)}.
$$

Solution

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

 Solution

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