13
$\begingroup$

In my research I have run into the following general problem: I have two distributions $P$ and $Q$ over the same domain, and a large (but finite) number of samples from those distributions. Samples are independently and identically distributed from one of these two distributions (though the distributions may be related: for example, $Q$ may be a mixture of $P$ and some other distribution.) The null hypothesis is that samples come from $P$, alternate hypothesis is that samples come from $Q$.

I am trying to characterize the Type I and Type II errors in testing the sample, knowing the distributions $P$ and $Q$. Particularly, I am interested in bounding one error given the other, in addition to the knowledge of $P$ and $Q$.

I have asked a question on math.SE regarding the relationship of Total Variation distance between $P$ and $Q$ to hypothesis testing, and received an answer that I accepted. That answer makes sense, but I still have not been able to wrap my mind around the deeper meaning behind the relationship of Total Variation distance and hypothesis testing as it relates to my problem. Thus, I decided to turn to this forum.

My first question is: is total variation bound on the sum of the probabilities of Type I and Type II errors independent of the hypothesis testing method that one employs? In essence, as long as there is a non-zero probability that the sample could have been generated by either one of the distributions, the probability of at least one of the errors must be non-zero. Basically, you can not escape the possibility that your hypothesis tester will make a mistake, no matter how much signal processing you do. And Total Variation bounds that exact possibility. Is my understanding correct?

There is also another relationship between Type I and II errors and the underlying probability distributions $P$ and $Q$: the KL divergence. Thus, my second question is: is KL-divergence bound only applicable to one specific hypothesis testing method (it seems to come up around the log-likelihood ratio method a lot) or can one apply it generally across all hypothesis testing methods? If it's applicable across all hypothesis testing methods, than why does it seem to be so very different from the Total Variation bound? Does it behave differently?

And my underlying question is: is there a prescribed set of circumstances when I should use either bound, or is it purely a matter of convenience? When should the result derived using one bound hold using the other?

I apologize if these questions are trivial. I am a computer scientist (so this seems like a fancy pattern matching problem to me :) .) I know information theory reasonably well, and have graduate background in probability theory as well. However, I am just starting to learn all of this hypothesis testing stuff. If needed, I will do my best to clarify my questions.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

Literature: Most of the answer you need are certainly in the book by Lehman and Romano. The book by Ingster and Suslina treats more advanced topics and might give you additional answers.

Answer: However, things are very simple: $L_1$ (or $TV$) is the "true" distance to be used. It is not convenient for formal computation (especially with product measures, i.e. when you have iid sample of size $n$) and other distances (that are upper bounds of $L_1$) can be used. Let me give you the details.

Development: Let us denote by

  • $g_1(\alpha_0,P_1,P_0)$ the minimum type II error with type I error$\leq\alpha_0$ for $P_0$ and $P_1$ the null and the alternative.
  • $g_2(t,P_1,P_0)$ the sum of the minimal possible $t$ type I + $(1-t)$ type II errors with $P_0$ and $P_1$ the null and the alternative.

These are the minimal errors you need to analyze. Equalities (not lower bounds) are given by theorem 1 below (in terms of $L_1$ distance (or TV distance if you which)). Inequalities between $L_1$ distance and other distances are given by Theorem 2 (note that to lower bound the errors you need upper bounds of $L_1$ or $TV$).

Which bound to use then is a matter of convenience because $L_1$ is often more difficult to compute than Hellinger or Kullback or $\chi^2$. The main example of such a difference appears when $P_1$ and $P_0$ are product measures $P_i=p_i^{\otimes n}$ $i=0,1$ which arise in the case when you want to test $p_1$ versus $p_0$ with a size $n$ iid sample. In this case $h(P_1,P_0)$ and the others are obtained easely from $h(p_1,p_0)$ (same for $KL$ and $\chi^2$) but you can't do that with $L_1$ ...

Definition: The affinity $A_1(\nu_1,\nu_0)$ between two measures $\nu_1$ and $\nu_2$ is defined as $$A_1(\nu_1,\nu_0)=\int \min(d\nu_1,d\nu_0) $$.

Theorem 1 If $|\nu_1-\nu_0|_1=\int|d\nu_1-d\nu_0|$ (half the TV dist), then

  • $2A_1(\nu_1,\nu_0)=\int (\nu_1+\nu_0)-|\nu_1-\nu_0|_1$.
  • $g_1(\alpha_0,P_1,P_0)=\sup_{t\in [0,1/\alpha_0]} \left ( A_1(P_1,tP_0)-t\alpha_0 \right )$
  • $g_2(t,P_1,P_0)=A_1(t P_0,(1-t)P_1)$

I wrote the proof here.

Theorem 2 For $P_1$ and $P_0$ probability distributions: $$\frac{1}{2}|P_1-P_0|_1\leq h(P_1,P_0)\leq \sqrt{K(P_1,P_0)} \leq \sqrt{\chi^2(P_1,P_0)}$$

These bounds are due to several well known statisticians (LeCam, Pinsker,...) . $h$ is the Hellinger distance, $K$ KL divergence and $\chi^2$ the chi-square divergence. They are all defined here. and the proofs of these bounds are given (further things can be found in the book of Tsybacov). There is also something that is almost a lower bound of $L_1$ by Hellinger ...

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Thank you for the answer, I am now trying to digest it. In my problem I have allowed Type I error. I also have the two distributions $P_0$ and $P_1$. I know that TV between them (as well as KL). So, what you are saying is that TV gives a tighter lower bound on Type II error than KL does, meaning that I should use TV for my analysis if I desire as tight of a lower bound as possible? $\endgroup$
    – M.B.M.
    Oct 20, 2011 at 18:54
  • $\begingroup$ And thank you for the Lehmann and Romano book suggestion, it looks very helpful and not too much over my head. Also, my library owns a copy! :) $\endgroup$
    – M.B.M.
    Oct 20, 2011 at 18:55
  • $\begingroup$ @Bullmoose what Theorem 1 says here is that TV (or L1) is related with equality to $A_1$ which is related with equality to g_2 or g_1 (the minimum sum of errors or type II error with controled type I). There are no inequalities here. Inequalities come when you need to go from L1 to Kullback. $\endgroup$
    – robin girard
    Oct 20, 2011 at 19:18
  • $\begingroup$ Unfortunately, I only have minimal background in measure theory. I think I sort of understand what $g_1$ and $g_2$ are, but I am not clear on $A_1$. Say I have two Gaussian distributions. The TV (or L1) between them is $$\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}\left|\frac{\exp(-x^2/2\sigma^2_1)}{\sigma_1}-\frac{\exp(-x^2/2\sigma^2_2)}{\sigma_2}\right|dx$$ But what would $A_1$ be? From definition, it looks like $$\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}\min\left(\frac{\exp(-x^2/2\sigma^2_1)}{\sigma_1},\frac{\exp(-x^2/2\sigma^2_2)}{\sigma_2}\right)dx$$ ... $\endgroup$
    – M.B.M.
    Oct 22, 2011 at 4:20
  • $\begingroup$ ... but how does $\int (\nu_1+\nu_2)$ map into this from the first bullet in the theorem? $\endgroup$
    – M.B.M.
    Oct 22, 2011 at 4:23
2
$\begingroup$

Answer to your first question: Yes, one minus the the total variation distance is a lower bound on the sum of the Type I + Type II error rates. This lower bound applies no matter what hypothesis testing algorithm you choose.

Justification: The answer you got on Math.SE gives the standard proof of this fact. Fix a hypothesis test. Let $A$ denote the set of outcomes on which this test will reject the null hypothesis (such a set must always exist). Then the calculation in the Math.SE answer proves the lower bound.

(Strictly speaking, this line of reasoning assumes that your hypothesis test is a deterministic procedure. But even if you consider randomized procedures, it is possible to show that the same bound still applies.)

Improve this answer
$\endgroup$
0

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.