3.2 Hypothesis Testing

I have considered several methods to evaluate error probabilities of hypothesis testing problems.

Lower bounds

Fano's inequality gives a lower bound on the mutual information between two random variables taking values on the same cardinality-M set:

I(X;Y) \geq P[X=Y] log M - h(P[X=Y])

This inequality holds provided that either X and Y are equiprobable. In hypothesis testing, Fano's inequality is used to lower bound the error probability for any M-ary test between equiprobable hypotheses in terms of the pairwise Kullback-Leibler divergence between the distributions.

T. S. Han and S. Verdú,"Generalizing the Fano Inequality,"
IEEE Trans. on Information Theory, vol. 40, no. 4, pp. 1247-1251, July 1994.

generalizes Fano's inequality by dropping the restriction that either random variable be equiprobable (and that M be finite). This generalization gives rise to several lower bounds on error probability.

S. Verdú, and T. S. Han, "A General Formula for Channel Capacity,"
IEEE Trans. on Information Theory, vol. 40, no. 4, pp. 1147-1157, July 1994.

gives a new converse channel coding theorem not based on Fano's inequality but on a new lower bound on the error probability of any M-ary test between equiprobable hypotheses:

for any \alpha \in [0,1] the error probability of a test for equiprobable X based on observations Y is lower bounded by:

P[ \pi (X|Y) \leq \alpha ] - \alpha

where \pi(X|Y) denotes the posterior probability of X given Y. A bound which is not only stronger but does away with the assumption that X is equiprobable is:

(1 - \alpha) P[ \pi (X|Y) \leq \alpha ] (*)

(The weaker bound for \alpha = 1/2 and equiprobable hypotheses was found by Shannon in 1957)

The bound (*) is due to

H. V. Poor and S. Verdú, "A Lower Bound on the Error Probability of Multihypothesis Testing,"
IEEE Trans. on Information Theory, vol. 41, no. 6, pp. 1992-1993, Nov. 1995.

A general upper-bound on the reliability (error-exponent) function of a noisy channel readily follows from the error probability lower bound. The Nov 1995 conjectures that that bound is in fact equal to the reliability function. The computation of that bound is a challenging large-deviations/optimization problem (even for the binary symmetric channel).

Poisson channel

S. Verdú,S. Verdú, "Asymptotic Error Probability of Binary Hypothesis Testing for Poisson Point-Process Observations,"
IEEE Trans. Information Theory, vol. IT-32, no. 1, p. 113-115, Jan. 1986.

considers a binary hypothesis testing problem with nonhomogeneous Poisson point process observations. The rate under hypothesis H_i is

\lambda_i (t) = b_i (t) + ( r_i (t) + z )^2

We show that the limit as z goes to infinity of the minimum error proability is equal to the complementary Gaussian cdf of the Hellinger distance between r_1 (t) and r_0 (t). In other words, asymptotically, the error probability is the same as for a binary white Gaussian problem where the signals are the square roots of r_1 (t) and r_0 (t).

This asymptotic setting models the regime of interest in heterodyne or homodyne optical coherent detection. The proof of the result in the Jan. 1986 paper is by change of measure and convergence of characteristic functions.

Worst-case error probability in binary hypothesis testing

Consider the equiprobable hypotheses:

H_1: Y = +1 + N
H_0: Y = -1 + N

where N is a random variable with standard deviation \sigma.

S. Shamai (Shitz) and S. Verdú, ``Worst-Case Power Constrained Noise for Binary-Input Channels,''
IEEE Trans. on Information Theory, vol. IT-38, pp. 1494-1511, Sep. 1992.

finds explicitly the worst-case probability of error over all distributions of N: it is a piecewise linear function of \sigma^2, and in particular, if \sigma <1, then the worst-case error probability is equal to \sigma^2 / 4. The least favorable noise distribution is shown to be the mixture of two lattice distributions with a finite number of atoms (which depends on \sigma).