3

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)?

Community
  • 1
M.B.M.
  • 1,059
  • 8
  • 18

1 Answers1

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

Thoughts?

M.B.M.
  • 1,059
  • 8
  • 18