# Error exponent in hypothesis testing

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)\}.$$

-

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?

-
I only have the first edition, but a look at Amazon appears to show that the order of Chapters 11 and 12 got swapped in the second edition. –  cardinal Jan 6 '12 at 4:55
@Dilip: Many thanks, I think I got the point now. Concerning my reasoning as exposed in my post: I realized that in (non Bayesian) hypothesis testing, one in general cannot have both error probabilities decrease at maximum rate, in other words, it appears that (1) and (2) cannot hold simultaneously for the same regions $A_n$. Concerning Cover-Thomas, in the 2nd edition Ch. 11 deals with hypotesis testing. The derivation of the optimal exponent for Bayesian h.t. (Chernoff inf.) is the one you outlined in your answer (so the definition of $P_\lambda$ is there, @Elvis). –  Michele Jan 6 '12 at 9:03
@Elvis: The distributions are over a common discrete set. $P_\lambda$ should just indicate a convex mixture of $P_1$ and $P_2$ with one of them having weight $\lambda$ and the other (obviously) $(1-\lambda)$. In this case, the mixture should correspond to the prior probabilities. –  cardinal Jan 6 '12 at 13:36
@Elvis: The definition of $P_\lambda$, for $\lambda\in [0,1]$, is, for each $x\in X$: $$P_\lambda(x) = \frac{P^\lambda_1(x)P^{1-\lambda}(x)}Z$$ where $Z$ is a normalization factor. Chernoff information $C(P_1,P_2)$ is $D(P_{\lambda^*}||P_1)$, for the (unique) $\lambda^*\in [0,1]$ s.t. $$D(P_{\lambda^*}||P_1)=D(P_{\lambda^*}||P_2)$$ (cf. p. 378--380 of Cover-Thomas, 2/e). –  Michele Jan 6 '12 at 17:28
@Michele Thanks, this is very nice. Welcome to the site! –  Elvis Jan 6 '12 at 17:33