= Solution
On $B$, part b gives $\log_2P_n=\log_2Q^n-\log_2Q^n(B)$. Hence the <information entropy> of the conditional law satisfies
$$
H(X_1^n)
=-\sum_{x_1^n\in B}P_n(x_1^n)\log_2Q^n(x_1^n)
+\log_2Q^n(B).
$$
Parts d and e imply
$$
\begin{aligned}
\log_2Q^n(B)
&=H(X_1^n)+\sum_{x_1^n\in B}P_n(x_1^n)\log_2Q^n(x_1^n)\\
&\leq nH(\overline P)+n\sum_{a\in A}\overline P(a)\log_2Q(a)\\
&=-nD(\overline P\Vert Q).
\end{aligned}
$$
Exponentiation proves $Q^n(B)\leq2^{-nD(\overline P\Vert Q)}$.
Back to article page
