On error probability bounds in Bayesian hypothesis testing

In the Bayesian version of (binary) hypothesis testing one has to decide which of two hypotheses $A$ and $B$ holds true. The two hypotheses are given prior probability $p(A)$ and $p(B)$, summing up to 1. $A$ and $B$ induce two probability distributions on a set of possible observations $X$, say $p(x|A)$ and $p(x|B)$. One has two decide between $A$ and $B$ after looking at one observation $x$.

It is known that the best strategy, that is the one that minimizes the probability of uncorrect guess, is to choose the hypothesis $H\in\{A,B\}$ that maximizes the $p(H|x)$, where $x$ is the observation. The probability of error (averaged on all $x$ and $H$) can be expressed

$$P_e = 1-\sum_x \max( p(x|A)p(A), p(x|B)p(B))\tag{1}$$

The expression (1) is often regarded as 'intractable' due to the presence of the max operator. Hence tractable bounds are seeked. An example is the harmonic lower-bound

$$P_e \geq E_x[P(A|x)P(B|x)]\tag{2}$$

($E_x$ is expectation over $x$; see e.g. : Routtenberg, Tabrikian, "A General Class of Lower Bounds on the Probability of Error in Multiple Hypothesis Testing", http://arxiv.org/abs/1005.2880, May 2010, and references therein).

My questions:

1) In what sense are expressions like the rhs of (2) "more tractable" than (1)? Computationally, they still require integration over (functions of the) PMF's $p(x|A)$ and $p(x|B)$. Maybe they are more convenient from an analytical point of view?

2) An exact and simple expressions for $P_e$ is:

$$P_e = 1-\frac{||p(\cdot|A)p(A) - p(\cdot|B)p(B)||_1 + 1}2\tag{3}$$

(Here $p(\cdot|H)$ is viewed as a vector in $R^{|X|}$, and $||\cdot||_1$ denotes the norm-1).

This is conceptually interesting because it relates probability of error to a distance between PMF's. Is this expression regarded as "intractable" in the same sense as (1)?

M.

• While (3) is expressed very concisely, it is not obvious that it is computable more easily because evaluating that $l_1$ norm requires computing $$|p(x|A)P(A) - p(x|B)P(B)|$$ for each possible value $x$ that the observation might take on. Thus, you must have available (say in a table) or must compute each $p(x|A)P(A)$ and $p(x|B)P(B)$, and once you have those, it seems no harder to add the $\max(p(x|A)P(A),p(x|B)P(B))$, the larger value, to an accumulator than to add $|p(x|A)P(A) - p(x|B)P(B)|$, the absolute value of the difference, to an accumulator. I must be missing something here..... Dec 31 '11 at 2:39
• Indeed, as I was pointed out, the interest in (3) is more conceptual than computational. But this leaves my first question open: what makes e.g. (2) more "tractable" than (1) or (3)? Dec 31 '11 at 7:51

It is known that the best strategy, that is the one that minimizes the probability of uncorrect guess, is to choose the hypothesis $H \in \{A,B\}$ that maximizes the $p(H|x)$, where $x$ is the observation.

As a personal peeve, I dislike this particular statement because in my mind it hides what is really going on, and makes what should be obvious rather obscure. Unfortunately, such Olympian pronouncements are what lots of people take away from a course on Bayesian methods....

Suppose that the observation $X$ is a discrete random variable. We observe that the event $\{X = x\}$ has occurred and need to decide choose between $A$ or $B$. But the observed event can be partitioned into $\{X = x, A\}$ and $\{X = x, B\}$ and we have that $$p(x) = p(X=x, A) + p(X=x, B).$$ Now, one of the two events $\{X = x, A\}$ and $\{X = x, B\}$ has occurred. Clearly if we choose $A$ upon observing $\{X = x\}$, we are correct with probability $p(X=x, A)$ and incorrect with probability $p(X=x, B)$ while if we choose $B$ upon observing $\{X = x\}$, we are correct with probability $p(X=x, B)$ and incorrect with probability $p(X=x, A)$. So, the probability of being incorrect in this instance is minimized if we choose $A$ if $p(X=x, B) < p(X=x, A)$ and choose $B$ if $p(X=x, B) > p(X=x, A)$. So, if $E$ and $C$ denote the events of the decision being in error and being correct respectively, we have that if the optimal (minimum-error probability) decision is made upon observing $\{X=x\}$, such occurrences contribute $\max\{p(X=x, A), p(X=x, B)\}$ to $P(C)$, and $\min\{p(X=x, A), p(X=x, B)\}$ to $P(E)$. We have \begin{align*} P(E) &= \sum_x \min\{p(X=x, A), p(X=x, B)\}\\ &= 1 - P(C)\\ &= 1 - \sum_x \max\{p(X=x, A), p(X=x, B)\} \end{align*} Since $p(X=x, A) = p(x|A)P(A)$ and $p(X=x, B) = p(x|B)P(B)$, we can write \begin{align*} P(E) &= 1 - \sum_x \max\{p(x|A)P(A), p(x|B)P(B)\}\\ &= 1 - \sum_x \max\left\{\frac{p(x|A)P(A)}{p(x)}, \frac{p(x|B)P(B)}{p(x)}\right\}p(x)\\ &= 1 - E_x\left[\max\{P(A|x),P(B|x)\}\right]\\ &= E_x\left[\min\{P(A|x),P(B|x)\}\right] \end{align*} where $E_x$ denotes expectation with respect to $x$. Alternatively, since $$\max\{p,q\} = \frac{p+q+|p-q|}{2},$$ we have \begin{align*} P(E) &= 1 - \sum_x \max\{p(x,A), p(x,B)\}\\ &= 1 - \sum_x \frac{p(x,A) + p(x,B)+ |p(x,A) - p(x,B)|}{2}\\ &= 1 -\frac{P(A) + P(B)}{2} - \sum_x \frac{|p(x,A) - p(x,B)|}{2}\\ &= 1 - \frac{1 + \sum_x |p(x|A)P(A) - p(x|B)P(B)|}{2}\\ &= 1 - \frac{||p(\cdot|A)p(A) - p(\cdot|B)p(B)||_1 + 1}2 \end{align*} as OP Michele writes it. Finally, for $p, q \in [0,1]$, $\min\{p, q\} \geq pq$ and so \begin{align*} P(E) &= E_x\left[\min\{P(A|x),P(B|x)\}\right]\\ &\geq E_x\left[P(A|x)P(B|x)\right]. \end{align*}

In summary, the three expressions for $P(E)$ appear different but are based on the same fundamental idea. All three require computation of an expectation with respect to $x$, and differ very little in computational complexity. Simplifications can be made if something specific is know about the variables, e.g. $X$ is a geometric random variable with different parameters under the two hypotheses in which case one could compute some sums analytically instead of numerically, but they would appear to apply equally in all three cases. I see very little difference in terms of computational tractability in (1)-(3) as exhibited in the OP's question.

• This is exactly what prompted my question: people seek for alternative expressions of (1) (see reference above for a review), but these expressions seem equivalent, at least computationally. Jan 1 '12 at 10:51
• I haven't thought the matter through or read the paper that you have cited, but perhaps for $M$-ary decision making when $M > 2$, the error probability expressions and bounds have different computational requirements? Jan 2 '12 at 16:39
• @DilipSarwate I really like your derivation of (3), and (for citation purposes) I am wondering whether you obtained that on your own or whether it's in a book... I also just posted a related question... Feb 22 '13 at 3:12
• @M.B.M. Thanks for the kind words. While I derived (3) without referring to any books or journals as I was composing my answer, I very much doubt that it was the first time this approach has been used by anyone or that this derivation has never been published somewhere by someone. If you want to cite my derivation, you might want to first read what others on this forum think in this discussion on meta.stats.SE. Feb 22 '13 at 12:46
• @DilipSarwate While the proof of (3) is not complicated, I just really appreciate someone taking the time to explain something. It is really helpful for us, novices, and I feel that not acknowledging it (even as a "helpful discussion") is unfair. So, thank you for clarification! (Btw, I may have solved my related question :)) Feb 23 '13 at 7:38

When $p(A) = p(B) = 1/2$, equation $(3)$ is basically computing the total variation distance (also known as the variation distance, for short). The variation distance is an ${\cal L}_1$ distance between two probability measures, which is why the ${\cal L}_1$ norm appears in your equation $(3)$.

It is well-known that the variation distance represents a lower bound on the sum $\Pr[\text{type I error}] + \Pr[\text{type II error}]$ for any hypothesis testing method, and this bound is tight for the hypothesis testing method you described. Therefore, the variation distance measures the minimum achievable error rate of hypothesis testing (again, when $p(A) = p(B) = 1/2$).

However, as you indicated, the variation distance can be difficult to calculate with. It is particularly annoying to deal with, if we might have multiple independent observations from the underlying distribution. Imagine that a referee secretly flips a coin to decide whether to use $A$ or $B$; then gives you $n$ independent draws from $p(x|A)$ (if he is using $A$) or $n$ independent draws from $p(x|B)$ (if he is using $B$), without telling you which. Your job is to decide whether he is using $A$ or $B$. What's the error rate of the optimal decision procedure for $n>1$, and how does it relate to the error rate for the case where $n=1$? This question is difficult to answer. It is not easy to relate the variation distance for the $n$-observation problem (the product measure, where $n>1$) to the variation distance for the single-observation case.

One way that people deal with this in practice is to look at some other distance metric, such as the KL divergence or $\chi^2$ or something, that is well-behaved with product measures: i.e., some distance metric where we can cleanly relate the distance for the $n$-observation case to the $1$-observation case (where we can cleanly relate the distance measure for a product measure to the distance for the underlying distribution). Then, we use some bound that relates that distance metric to the variation distance, and Bob's our uncle.