= Solution
Let $P\ne Q$ be <probability mass functions> on a finite <alphabet>, with $P$ absolutely continuous with respect to $Q$. A decision region $B_n$ accepts the null law $P^{\otimes n}$. Write
$$
\alpha_n=P^{\otimes n}(B_n^c),\qquad
\beta_n=Q^{\otimes n}(B_n)
$$
for its type-I and type-II errors. <Stein's lemma (information theory)> states that for every fixed $0<\varepsilon<1$,
$$
\lim_{n\to\infty}-\frac1n\log
\inf_{B_n:\,\alpha_n\leq\varepsilon}\beta_n
=D(P\Vert Q),
$$
where logarithms and <relative entropy> use base two.
For achievability, let
$$
B_n=\left\{x_1^n:\frac1n\log
\frac{P^{\otimes n}(x_1^n)}{Q^{\otimes n}(x_1^n)}
\geq D(P\Vert Q)-\eta\right\}.
$$
Under $P^{\otimes n}$, the normalized log-likelihood ratio converges in probability to $D(P\Vert Q)$ by the <weak law of large numbers>, so $alpha_n\to0$. On $B_n$, $Q^{\otimes n}\leq2^{-n(D(P\Vert Q)-\eta)}P^{\otimes n}$, whence $\beta_n\leq2^{-n(D(P\Vert Q)-\eta)}$.
For the converse, let
$$
A_n=\left\{x_1^n:\frac1n\log
\frac{P^{\otimes n}(x_1^n)}{Q^{\otimes n}(x_1^n)}
\leq D(P\Vert Q)+\eta\right\}.
$$
Again $P^{\otimes n}(A_n)\to1$. If $alpha_n\leq\varepsilon$, then
$$
\beta_n\geq Q^{\otimes n}(B_n\cap A_n)
\geq2^{-n(D(P\Vert Q)+\eta)}P^{\otimes n}(B_n\cap A_n).
$$
The final factor has positive lower limit at least $1-\varepsilon$. Taking exponential rates and then $eta\downarrow0$ proves the converse and the lemma.
Solved by gpt-5.6-sol high.
Back to article page
