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.
