I am wondering if one can relate the KL divergence to the probability of error in a Bayesian binary hypothesis testing setting. That is, we have to decide between hypotheses $A$ and $B$ given observationx, and we have prior probabilities of either being true $p(A)$ and $p(B)$ such that $p(A)+p(B)=1$. Under either $A$ or $B$, observation induces (different) probability distributions $p_A(x)$ and $p_B(x)$.

The setting is identical to a previous question, and this question may be considered its extension. The following restatement of eq. (3) from the previous question lower-bounds the probability of error of the hypothesis test:

$$P_e = \frac{1-||p_A(x)p(A) - p_B(x)p(B)||_1}2\tag{1}$$

where $||\cdot||_1$ denotes the $L_1$ norm. When the prior probabilities are equal, that is $P(A)=P(B)=\frac{1}{2}$, (1) reduces to the expression involving the total variation distance between probability distributions induces by the two hypothesis:

$$P_e = \frac{1-\frac{1}{2}||p_A(x) - p_B(x)||_1}2\tag{2}$$

Pinsker's inequality states that

$$||p_A(x) - p_B(x)||_1\leq\sqrt{2D(p_A(x)||p_B(x))}\tag{3}$$ where $D(p_A(x)||p_B(x))=\sum_x p_A(x)\log\frac{p_A(x)}{p_B(x)}$.

Of course (3) can be used to lower-bound (2) as follows:

$$P_e \geq \frac{1-\frac{1}{\sqrt{2}}\sqrt{D(p_A(x)||p_B(x))}}2\tag{4}$$

However, I am wondering if a similar KL-divergence based lower bound can be derived for (1). Does weighting by the priors work in this case, i.e. is (5) true:

$$||p_A(x)p(A) - p_B(x)p(B)||_1\leq\sqrt{2D(p_A(x)p(A)||p_B(x)p(B))}\tag{5}$$

I don't think it is true. So, is there a KL-divergence based lower-bound for (1)?


1 Answer 1


Ok, I am answering the question I posed myself, but might the following work?

Denote $p(A)=\pi_A$ and $p(B)=\pi_B$ for brevity. Using the triangle inequality for $L_1$ norm, we can obtain:

$$\begin{array}{rcl}||p_A(x)\pi_A - p_B(x)\pi_B||_1&\leq&||p_A(x)\pi_A-p_B(x)\pi_A||_1+||p_B(x)\pi_A-p_B(x)\pi_B||_1\\&=&\pi_A||p_A(x)-p_B(x)||_1+|\pi_A-\pi_B|\end{array}$$ with the equality holding true because $\pi_A>0$ and the $L_1$ norm of a distribution is one.

We can then upper-bound $||p_A(x)-p_B(x)||_1$ using the Pinsker's Inequality.

Note that the equality holds for the equiprobable priors $\pi_A=\pi_B=\frac{1}{2}$.



Your Answer

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

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