Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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


share|cite|improve this question
You might try based on your two questions. In particular, I notice Robin Girard is more active there than here. – Will Jagy Dec 30 '11 at 22:31
As requested,… – Will Jagy Dec 30 '11 at 22:54
Many thanks. NB: edited my post to rectify formula (3): the previous formulation was probability of success, not of error. M. – Michele Dec 30 '11 at 23:06
(1) differs from the same expression in the linked paper (also expression (1) there). In the paper they take the expectation of the maximum over the true distribution of $x$. Here you are just summing over $x$ (equivalently, assuming the uniform PMF). Is the difference intentional? – R Hahn Dec 30 '11 at 23:07
There is no difference. The formula in the cited paper (instantiated to the case $M=2$, binary h.t.) is $$ P_e = 1-E_x[\max_{i=1,2} p(\theta_i|x)] $$ where, in our case, $\theta_1=A$ and $\theta_2=B$. If you use Bayes, the probabilities $p(x)$ of the expectation and in $p(\theta_i|x)= p(x|\theta_i)p(\theta_i)/p(x)$ cancel out, and you get the same as my (1). M. – Michele Dec 30 '11 at 23:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.