2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – Ashok
    Jan 6, 2012 at 11:35
  • $\begingroup$ @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. $\endgroup$
    – Michele
    Jan 6, 2012 at 18:55
  • $\begingroup$ @Michele: Yeh, sorry. I just overlooked the things. Very good discussion. I got to know several things from this. Thank you. $\endgroup$
    – Ashok
    Jan 7, 2012 at 6:57

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.