Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Kullback-Leibler divergence (a.k.a. relative entropy) has a nice property in hypothesis testing: given some observed measurement $m\in \mathcal{Q}$, and two probability distributions $P_0$ and $P_1$ defined over measurement space $\mathcal{Q}$, if $H_0$ is the hypothesis that $m$ was generated from $P_0$ and $H_1$ is the hypothesis that $m$ was generated from $P_1$, then the Type I and Type II errors are related as follows:

$$d(\alpha,\beta)\leq D(P_0\|P_1)$$

where

$$D(P_0\|P_1)=\sum_{x\in\mathcal{Q}}P_0(x)\log_2\left(\frac{P_0(x)}{P_1(x)}\right)$$

is the Kullback-Leibler divergence,

$$d(\alpha,\beta)=\alpha\log_2\frac{\alpha}{1-\beta}+(1-\alpha)\log_2\frac{1-\alpha}{\beta}$$

is called binary relative entropy, and $\alpha$ and $\beta$ are probabilities of Type I and Type II errors, respectively.

This relationship allows one to bound the probabilities of Type I and Type II errors.

I am wondering if something similar exists for Total Variation distance:

$$TV(P_0,P_1)=\frac{1}{2}\sum_{x\in\mathcal{Q}}\left| P_0(x)-P_1(x)\right|$$

I am aware that

$$2(TV(P_0,P_1)^2\leq D(P_0\|P_1)$$

Is there more?

Unfortunately, I am not very well-versed in hypothesis testing and statistics (I know the basics and have pretty good background in probability theory). Any help would be appreciated.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Here's a bit of an informal argument towards a lower bound I recently learned during a lecture.

Suppose we have two probability measures $P_0(\cdot )$ and $P_1(\cdot )$, and suppose I reject $P_0$ when the event $A$ occurs. So,

$ \begin{align} \textrm{Type I error} + \textrm{Type II error} &= P_0(A) + P_1(A^C) \\ &= P_0(A) + [1 - P_1(A)]\\ &= 1 + [P_0(A) - P_1(A)]\\ &\geq 1 + \inf_{A}[P_0(A)-P_1(A)]\\ &= 1-\sup_{A}[P_0(A)-P_1(A)]\\ &= 1-TV(P_0 , P_1) \end{align}$

share|improve this answer
    
this is a neat answer -- thank you very much! I am just curious, for what class was this lecture and what textbook (if any) is used for this class? I think that your argument is formal enough, and it is definitely useful (as it lower-bounds the hypothesis testing errors), but I would like to read the material "in the neighborhood" of this... –  M.B.M. Oct 16 '11 at 2:22
    
It's an Asymptotics course taught by Mark Low. No textbook, though. We basically discuss a lot of the research he's done in the last 15 or so years, so his publications would be the equivalent of the course textbook. –  Mike Wierzbicki Oct 16 '11 at 14:06
    
There's a very small subtlety hiding in the step that leads to the RHS of the fourth equality. Writing that as $1 - \sup_A[P_1(A) - P_0(A)]$ makes it slightly clearer. –  cardinal Oct 21 '11 at 9:58
    
@cardinal I believe you're right. There's another subtle step hidden: $TV(P_0, P_1)=\sup_A (|P_0 - P_1|)$, so you need to convince your self that $\sup_A (|P_0 - P_1|)=\sup_A (P_0 - P_1)$ (which doesn't take much convincing). –  Mike Wierzbicki Oct 21 '11 at 12:43

Your Answer

 
discard

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

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