= Solution
The <Neyman-Pearson lemma> gives an optimal acceptance region for $P$ of the form
$$
B_n(\tau)=\left\{x_1^n:\frac{P^{\otimes n}(x_1^n)}{Q^{\otimes n}(x_1^n)}\geq\tau\right\},
$$
with possible boundary randomization. If $\widehat P_n$ is the empirical mass function, then
$$
\frac1n\log\frac{P^{\otimes n}(x_1^n)}{Q^{\otimes n}(x_1^n)}
=D(\widehat P_n\Vert Q)-D(\widehat P_n\Vert P),
$$
so equivalently
$$
B_n(\tau)=\left\{D(\widehat P_n\Vert Q)-D(\widehat P_n\Vert P)\geq n^{-1}\log\tau\right\}.
$$
Back to article page
