# What is the relationship of $\mathcal{L}_1$ (total variation) distance to hypothesis testing?

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.

-

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