4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – M.B.M. Oct 16 '11 at 2:22
  • $\begingroup$ 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. $\endgroup$ – user13888 Oct 16 '11 at 14:06
  • 1
    $\begingroup$ 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. $\endgroup$ – cardinal Oct 21 '11 at 9:58
  • $\begingroup$ @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). $\endgroup$ – user13888 Oct 21 '11 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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