Error exponent in hypothesis testing

Question

In hypothesis testing, one must decide between two probability distributions $P_1(x)$ and $P_2(x)$ on a finite set $X$, after observing $n$ i.i.d. samples $x_1,...,x_n$ drawn from the unknown distribution. Let $A_n\subseteq X^n$ denote the chosen acceptance region for $P_1$. The error probabilities of type I and II can be expressed thus

$$ \alpha_n = P^n_1(A^c_n)$$ $$ \beta_n = P^n_2(A_n)$$

(Cover & Thomas, Ch. 11 is an excellent reference for the definitions and facts mentioned in this post).

Assume we have chosen the acceptance regions $A_n$'s ($n\geq 1$), so that both error probabilities approach zero as the number of observations grows: $\alpha_n\rightarrow 0$ and $\beta_n\rightarrow 0$ as $n\rightarrow \infty$. Stein's Lemma tells us that the maximum rate of deacrease of both error probabilities is determined, to the first order of the exponent, by the the KL-distance between the given distributions. More precisely

$$ -\frac 1 n \log \alpha_n \rightarrow D(P_2||P_1)\tag{1}$$ $$ -\frac 1 n \log \beta_n \rightarrow D(P_1||P_2)\tag{2}$$

Now, consider the Bayesian version of the hypothesis testing problem. In this case, $P_1$ and $P_2$ are given prior probabilities $\pi_1$ and $\pi_2$, respectively, and the error probability is obtained by weighting $\alpha_n$ and $\beta_n$:

$$ e_n = \pi_1\alpha_n + \pi_2\beta_n.\tag{3}$$

In this case, the optimal exponent for $e_n$ is given by Chernoff distance between the given distributions:

$$ -\frac 1 n \log e_n \rightarrow C(P_1,P_2).$$

Question: what is wrong in the reasoning below? (Disclaimer: I'm not trying to be fully formal/detailed here).

By (3), the decrease rate of $e_n$ is the minimum deacrease rate of $\alpha_n$ and $\beta_n$:

$$ \lim -\frac 1 n \log e_n = \min\{\lim -\frac 1 n \log \alpha_n, \lim -\frac 1 n \log \beta_n\}$$.

Since $e_n\rightarrow 0$, one must have both $\alpha_n\rightarrow 0$ and $\beta_n\rightarrow 0$ as $n\rightarrow \infty$. So, by the previous considerations on Stein's Lemma, and (1) and (2), one would get

$$ \lim -\frac 1 n \log e_n = \min\{D(P_1||P_2), \,\,D(P_2||P_1)\}$$

which is quite different from $C(P_1,P_2)$.

EDIT: I realize that now that (1) and (2) cannot hold simultaneously, for the same regions $A_n$'s, so this must be the bug in the reasoning.

What one can infer through a similar reasoning is just, I think,

$$C(P_1,P_2)\leq \min\{D(P_1||P_2), \,\,D(P_2||P_1)\}.$$

Answer 1

Essentially, the answer to your question is that the behavior of $\alpha_n$ and $\beta_n$ is somewhat different when the Bayesian minimum-error-probability rule is used and one is trying to minimize $e_n$. This is because the decision regions $A_n$ and $A_n^c$ are different. In contrast to your (1) and (2), the behavior is of the form

$$\begin{align*} -\frac{1}{n}\log \alpha_n &\rightarrow D(P_\lambda||P_1)\\ -\frac{1}{n} \log \beta_n &\rightarrow D(P_\lambda ||P_2) \end{align*}$$

so that

$$ \lim -\frac{1}{n} \log e_n = \min\{D(P_\lambda||P_1), \,\,D(P_\lambda||P_2)\}. $$

Since $D(P_\lambda||P_1)$ is an increasing function of $\lambda$ while $D(P_\lambda||P_2)$ is a decreasing function of $\lambda$, choosing $\lambda$ such that $D(P_\lambda||P_1)=D(P_\lambda||P_2)$ gives $C(P_1,P_2)$.

All this is described in Chapter 12 of the first edition of Cover and Thomas. Has it been deleted in the second edition since you refer us to Chapter 11 of Cover and Thomas?