## Return to Question

4 added 2 characters in body; added 7 characters in body

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 = \frac{||p(\cdot|A)p(A) 1-\frac{||p(\cdot|A)p(A) - p(\cdot|B)p(B)||_1 + 1}2$$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. 3 displayed TeX 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 P_e = 1-\sum_x \max( p(x|A)p(A), p(x|B)p(B)) (1)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$P_e \geq E_x[P(A|x)P(B|x)]$(2)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 P_e = \frac{||p(\cdot|A)p(A) - p(\cdot|B)p(B)||_1 + 1}21}2$$ (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. 2 edited body; deleted 6 characters in body 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$) is can be expressed$P_e = 1-\sum_x \max( p(x|A)p(A), p(x|B)p(B))$(1) The expression (1) is often regarded to be 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)]$(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 = \frac{||p(\cdot|A)p(A) - p(\cdot|B)p(B)||_1 + 1}2$(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 "untractable" intractable" in the same sense as (1)?

M.

1