Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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: I'm having hard time trying to reconcile Stein's Lemma with Bayesian h.t. In particular, consider the reasoning below: what is wrong with it? (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)$.

share|improve this question
    
Why should $\lim -\frac 1 n \log e_n = \min{\lim -\frac 1 n \log \alpha_n, \lim -\frac 1 n \log \beta_n}$? Suppose $\alpha_n \approx e^{-an}$ and $\beta_n \approx e^{-bn}$ for some $a>b>0$ and $\pi_1=1/2=\pi_2$ then the l.h.s. is $a+b$ whereas the r.h.s. is $b$. –  Ashok Jan 6 '12 at 11:35
    
@Ashok: in your example, write en as $$\pi_2e^{−bn}(\frac{\pi_1}{\pi_2}e^{−(a−b)n}+1)$$ then take the $-\frac 1 n \log$: the limit is $b$, not $a+b$. This is not the bug in the reasoning: see my post and the discussion at stats.stackexchange link. –  Michele Jan 6 '12 at 18:55
    
@Michele: Yeh, sorry. I just overlooked the things. Very good discussion. I got to know several things from this. Thank you. –  Ashok Jan 7 '12 at 6:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.