MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.