Statistical Hypothesis Testing: Problems 1.3 2003/06/04 2003/08/25 17:27:41.417 GMT-5 Don Johnson dhj@rice.edu Don Johnson dhj@rice.edu Eileen Krause erkrause@rice.edu Kyle Clarkson kclarks@rice.edu Elizabeth Gregory lizzardg@rice.edu Kevin Duh kevinduh@rice.edu Mariyah Poonawala mariyah@rice.edu Matthew Jeanes mjeanes@rice.edu Jeffrey Silverman jsilv@rice.edu Consider the following two-model evaluation problem (van Trees; prob.2.2.1). ℳ 0 :   r n ℳ 1 :   r s n where s and n are statistically independent, positively valued, random variables having the densities p s s a a s and p n n b b n

Prove that the likelihood ratio test reduces to r ≷ ℳ 0 ℳ 1 γ

Find γ for the minimum probability of error test as a function of the a priori probabilities.

Now assume that we need a Neyman-Pearson test. Find γ as a function of P F , the false-alarm probability.

The two models describe different equi-variance statistical models for the observations (van Trees; Prob. 2.2.11). ℳ 0 :   p r r 1 2 2 r ℳ 1 :   p r r 1 2 1 2 r 2

Find the likelihood ratio.

Compute the decision regions for various values of the threshold in the likelihood ratio test.

Assuming these two densities are equally likely, find the probability of making an error in distinguishing between them.

A hypothesis testing criterion radically different from those discussed in this section and this section is minimum equivocation. In this information theoretic approach, the two-model testing problem is modeled as a digital channel, shown in this figure. The channel's inputs, generically represented by the x , are the models and the channel's ouputs, denoted by y , are the decisions. The quality of such information theoretic channels is quantified by the mutual information x y defined to be the difference between the entropy of the inputs and the equivocation (Cover and Thomas; sections 2.3, 2.4). x y H x H x | y H x i i P x i P x i H x | y i j i j P x i y j P x i y j P y j Here, P x i denotes the a priori probabilities, P y j the output probabilities, and P x i y j the joint probability of input x i resulting in output y j . For example, P x 0 y 0 P x 0 1 P F and P y 0 P x 0 1 P F P x 1 1 P D . For a fixed set of a priori probabilities, show that the decision rule that maximizes the mutual information is the likelihood ratio test. What is the threshold when this criterion is employed? This problem is relatively difficult. The key to its solution is to exploit the concavity of the entropy function. Non-Gaussian statistical models sometimes yield surprising results in comparison to Gaussian ones. Consider the following hypothesis testing problem where the observations have a Laplacian probability distribution. ℳ 0 :   p r r 1 2 r m ℳ 1 :   p r r 1 2 r m

Find the sufficient statistic for the optimal decision rule.

What decision rule guarantees that the miss probability will be less than 0.1?

Developing a Neyman-Pearson decision rule for more than two models has not been detailed. Assume K distinct models are required to account for the observations. We seek to maximize the probability of correctly announcing ℳ i under the constraint that the probability of announcing ℳ i when model ℳ 0 was indeed true does not exceed a specified value.

Formulate the optimization problem that simultaneously maximizes ℳ i say ℳ i under the constraint ℳ 0 say ℳ i α i . Find the solution using Lagrange multipliers.

Show that your solution can be expressed as choosing the largest of the sufficient statistics ϒ i r C i .

Pattern recognition relies heavily on ideas derived from the principles of statistical model testing. Measurements are made of a test object and these are compared with those of "standard" objects to determine which the test object most closely resembles. Assume that the measurement vector r is jointly Gaussian with mean m i ( i 1 … K ) and covariance matrix σ 2 I (i.e., statistically independent components). Thus there are K possible objects, each having an "ideal" measurement vector m i and probability P i of being present.

How is the minimum probability of error choice of object determined from the observation of r ?

Assuming that only two equally likely objects are possible ( K 2 ), what is the probability of error of your decision rule?

The expense of making measurements is always a practical consideration. Assuming each measurement costs the same to perform, how would you determine the effectiveness of a measurement vector's component?

Define y to be y k 0 L x k where the x k are statistically independent random variables, each having a Gaussian density 0 σ 2 . The number L of variables in the sum is a random variable with a Poisson distribution. L l λ l l λ where l 0 1 … Based upon the observation of y , we want to decide whether L 1 or L 1 . Write an expression for the minimum P e . One observation of the random variable r is obtained. This random variable is either uniformly distributed between -1 and +1 or expressed as the sum of statistically independent random variables, each of which is also uniformly distributed between -1 and +1.

Suppose there are two terms in the aforementioned sum. Assuming that the two models are equally likely, find the minimum probability of error decision rule.

Compute the resulting probability of error of your decision rule.

Show that the decision rule found in this previous part applies no matter how many terms are assumed present in the sum.

The observed random variable r has a Gaussian density on each of five models. p r ℳ i r 1 2 σ r m i 2 2 σ 2 for i 1 2 … 5 , where m 1 -2 m , m 2 m , m 3 0 , m 4 m , m 5 2 m . The models are equally likely and the criterion of the test is to minimize P e .

Draw the decision regions on the r -axis.

Compute the probability of error.

Let σ 1 . Sketch accurately P e as a function of m .

The goal is to choose which of the following four models is true upong the reception of the three-dimensional vector r (van Trees; Prob. 2.6.6). ℳ 0 :   r m 0 n ℳ 1 :   r m 1 n ℳ 2 :   r m 2 n ℳ 3 :   r m 3 n where m 0 a 0 b ,   m 1 0 a b ,   m 2 a 0 b ,   m 3 0 a b The noise vector n is a Gaussian random vector having statistically independent, identically distributed components, each of which has zero mean and variance σ 2 . We have L independent observations of the received vector r .

Assuming equally likely models, find the minimum P e decision rule.

Calculate the resulting error probability.

Show that neither the decision rule nor the probability of error do not depend on b . Intuitively, why is this fact true?

To gain some appreciation of some of the issues in implementing a detector, this problem asks you to program (preferably in Matlab) a simple detector and numerically compare its performance with theoretical predictions. Let the observations consist of a signal contained in additive Gaussian white noise. ℳ 0 :   r l n l    l 0 … L 1 ℳ 1 :   r A 2 l L n l    l 0 … L 1 The variance of each noise value equals σ 2 .

What is the theoretical false-alarm probability of the minimum P e detector when the hypotheses are equally likely?

Write a Matlab program that estimates the false-alarm probability. How many simulation trials are needed to accurately estimate the false-alarm probability? Choose values for A and σ 2 that will result in values for P F of 0.1 and 0.01. Estimate the false-alarm probability and compare with the theoretical value in each case.

Calculate the Kullback-Leibler distance between the following pairs of densities. Use these results to find the Fisher information for the mean parameter m .

Jointly Gaussian random vectors having the same covariance matrix but dissimilar mean vectors.

Two Poisson random variables having average rates λ 0 and λ 1 . In this example, the observation time T plays the role of the number of observations.

Two sequences of statistically independent Laplacian random variables having the same variance but different means.

Plot the Kullback-Leibler distances for the Laplacian case and for the Gaussian case of statistically independent random variables. Set the variance equal to σ 2 in each case and plot the distances as a function of m σ .

The Kullback-Leibler and Chernoff distances can be related to the Fisher information matrix. Let p r ; θ r ; θ be a probability density that depends on the parameter vector θ We want to consider the distance between probability densities that differ by a perturbation δ θ in their parameter vectors.

Show that ∝ p r ; θ 0 + δ θ r ; θ 0 + δ θ p r ; θ r ; θ δ θ F θ 0 δ θ for small δ θ . What is the constant of proportionality?

What is the Chernoff distance between these distributions?

Deduce from the Kullback-Leibler distance for the Gaussian and Poisson cases what the Cramér-Rao bound is for estimating the mean and average rate, respectively.

Insights into certain detection problems can be gained by examining the Kullback-Leibler distance and the properties of Fisher information. We begin by first showing that the Gaussian distribution has the smallest Fisher information for the mean parameter for all differentiable distributions having the same variance.

Show that if f t and g t are linear functions of t and g t is positive for 0 t 1 , then the ratio f t 2 g t is convex over this interval.

Use this property to show that the Fisher information is a convex function of the probability density.

Define p t x ; θ 1 t p 0 x ; θ t p 1 x ; θ , 0 t 1 , where p 0 x ; θ p 1 x ; θ 𝒫 , a class of densities having variance one. Show that this set is convex.

Because of the Fisher information's convexity, a given distribution p 0 x | θ 𝒫 minimizes the Fisher information if and only if t F t 0 at t 0 for all p 1 x | θ 𝒫 . Let the parameter be the expected value of all densities in 𝒫 . By using Lagrange multipliers to impose the constant variance constraint on all densities in the class, show that the Gaussian uniquely minimizes Fisher information.

What does this result suggest about the performance probabilities for problems wherein the models differ in mean?

Find the Chernoff distance between the following distributions.

Two Gaussian distributions having the same variance but different means.

Two Poisson distributions having differing parameter values.

Let's explore how well Stein's Lemma predicts optimal detector performance probabilities. Consider the two-model detection problem wherein L statistically independent, identically distributed Gaussian random variables are observed. Under ℳ 0 , the mean is zero and the variance one; under ℳ 1 , the mean is one and the variance one.

A binary symmetric digital communications channel.

Find an expression for the false-alarm probability P F when the miss probability is constrained to be less than α .

Find the Kullback-Leibler distance corresponding to the false-alarm probability's exponent.

Plot the exact error for values of α 0.1 and α 0.01 as a function of the number of observations. Plot on the same axes the result predicted by Stein's Lemma.

We observe a Gaussian random variable r . This random variable has zero mean under model ℳ 0 and mean m under ℳ 1 . The variance of r in either instance is σ 2 . The models are equally likely.

What is an expression for the probability of error for the minimum P e test when one observation of r is made?

Assume one can perform statistically independent observations of r . Construct a sequential decision rule which results in P e equal to one-half of that found in this previous part.

What is the sufficient statistic in this previous part and sketch how the thresholds for this statistic vary with the number of trials. Assume that m 10 and that σ 1 . What is the expected number of trials for the sequential test to terminate?

The optimum reception of binary information can be viewed as a model testing problem. Here, equally-likely binary data (a "zero" or a "one") is transmitted through a binary symmetric channel. The indicated parameters denote the probabilities of receiving a binary digit given that a particular digit was sent. Assume that ε 0.1 .

Assuming a single transmission for each digit, what is the minimum probability of error receiver and what is the resulting probability of error?

One method of improving the probability of error is to repeat the digit to be transmitted L times. This transmission scheme is equivalent to the so-called repetition code. The receiver uses all of the received L digits to decide what was actually sent. Assume that the results of each transmission are statistically independent of all others. Construct the minimum probability of error receiver and find an expression for P e in terms of L .

Assume that we desire the probability of error to be 10 -6 . How long a repetition code is required to achieve this goal for the channel given above? Assume that the leading term in the probability of error expression found in this previous part dominates.

Construct a sequential algorithm which achieves the required probability of error. Assume that the transmitter will repeat each digit until informed by the receiver that it has determined what digit was sent. What is the expected length of the repetition code in this instance?

You have accepted the (dangerous) job of determining whether the radioactivity levels at the Chernobyl reactor are elevated or not. Because you want to stay as short a time as possible to render you professional opinion, you decide to use a sequential-like decision rule. Radioactivity is governed by Poisson probability laws, which means that the probability that n counts are observed in T seconds equals n λ T n λ T n where λ is the radiation intensity. Safe radioactivity levels occur when λ λ 0 and unsafe ones at λ λ 1 , λ 1 λ 0 .

Construct a sequential decision rule to determine whether it is safe or not. Assume you have defined false-alarm and miss probabilities according to accepted "professional standards." According to these standards, these probabilities equal each other.

What is the expected time it will take to render a decision?

Sequential tests can be used to advantage in situations where analytic difficulties obscure the problem. Consider the case where the observations either contain no signal ( ℳ 0 ) or a signal whose components are randomly set to zero. ℳ 0 :   r l n l ℳ 1 :   r l a l s l where a l 1 p 0 1 p The probability that a signal value remains intact is a known quantity p and "drop-outs" are statistically independent of each other and of the noise. This kind of model is often used to describe intermittent behavior in electronic equipment.

Find the likelihood ratio for the observations.

Develop a sequential test that would determine whether a signal is present or not.

Find a formula for the test's thresholds in terms of P F and P D .

How does the average number of observations vary with p ?

In some cases it might be wise to not make a decision when the data do not justify it. Thus, in addition to declaring that one of two models occurred, we might declare "no decision" when the data are indecisive. Assume you observe L statistically independent observations r l , each of which is Gaussian and has a variance of two. Under one model the mean is zero, and under the other the mean is one. The models are equally likely to occur.

Construct a hypothesis testing rule that yields a probability of no-decision no larger than some specified value α , maximizes the probabilities of making correct decisions when they are made, and makes these correct-decision probabilities equal.

What is the probability of a correct decision for your rule?

You decide to flip coins with Sleazy Sam. If heads is the result of a coin flip, you win one dollar; if tails, Sam wins a dollar. However, Sam's reputation has preceded him. You suspect that the probability of tails, p , may not be 12 . You want to determine whether a biased coin is being used or not after observing the results of three coin tosses.

You suspect that p 34 . Assuming that the probability of a biased coin equals that of an unbiased coin, how would you decide whether a biased coin is being used or not in a "good" fashion?

Using your decision rule, what is the probability that your determination is incorrect?

One potential flaw with your decision rule is that a specific value of p was assumed. Can a reasonable decision rule be developed without knowing p ? If so, demonstrate the rule; if not, show why not.

When a patient is screened for the presence of a disease in an organ, a section of tissue is viewed under a microscope and a count of abnormal cells made. Even under healthy conditions, a small number of abnormal cells will be present. Presumably a much larger number will be present if the organ is diseased. Assume that the number L of abnormal cells in a section is geometrically distributed. L l 1 α α l for l 0 1 … . The parameter α of a diseased organ will be larger than that of a healthy one. The probability of a randomly selected organ being diseased is p .

Assuming that the value of the parameter α is known in each situation, find the best method of deciding whether an organ is diseased.

Using your method, a patient was said to have a diseased organ. In this case, what is the probability that the organ is diseased?

Assume that α is known only for healthy organs. Find the disease screening method that minimizes the maxmimum possible value of the probability that the screening method will be in error.

How can the standard sequential test be extended to unknown parameter situations? Formulate the theory, determine the formulas for the thresholds. How would you approach finding the average number of observations? A common situation in statistical signal processing problems is that the variance of the observations is unknown (there is no reason that noise should be nice to us!). Consider the two Gaussian model testing problem where the models differ in their means and have a common, but unknown variance. ℳ 0 :   r 0 σ 2 I ℳ 1 :   r m σ 2 I σ 2 ?

Show that the unknown variance enters into the optimum decision only in the threshold term.

In the (happy) situation where the threshold η equals one, show that the optimum test does not depend on σ 2 and that we did not need to know its value in the first place. When will η equal one?

Consider the following composite hypothesis testing problem (van Trees; Prob. 2.5.2). ℳ 0 :   p r r 1 2 σ 0 r 2 2 σ 0 2 ℳ 1 :   p r r 1 2 σ 1 r 2 2 σ 1 2 where σ 0 is known but σ 1 is known only to be greater than σ 0 . Assume that we require that P F 10 -2 .

Does an UMP test exist for this problem? If it does, find it.

Construct a generalized likelihood ratio test for this problem. Under what conditions can the requirement on the false-alarm probability be met?

Data are often processed "in the field," with the results from several systems sent to a central place for final analysis. Consider a detection system wherein each of N field radar systems detects the presence or absence of an airplane. The detection results are collected together so that a final judgment about the airplane's presence can be made. Assume each field system has false-alarm and detection probabilities P F and P D respectively.

Find the optimal detection strategy for making a final determination that maximizes the probability of making a correct decision. Assume that the a priori probabilities π 0 , π 1 of the airplane's absence or presence, respectively, are known.

How does the airplane detection system change when the a priori probabilities are not known? Require that the central judgment have a false-alarm probability no bigger than P F N .

Mathematically, a preconception is a model for the "world" that you believe applies over a broad class of circumstances. Clearly, you should be vigilant and continually judge your assumption's correctness. Let X l denote a sequence of random variables that you believe to be independent and identically distributed with a Gaussian distribution having zero mean and variance σ 2 . Elements of this sequence arrive one after the other, and you decide to use the sample average M n as a test statistic. M l 1 l i 1 l X i

Based on the sample average, develop a procedure that test for each n whether the preconceived model is correct. This test should be designed so that it continually monitors the validity of the assumptions, and indicates at each n whether the preconception is valid or not. Establish this test so that it yields a constant probability of judging the model incorrect when, in fact, it is actually valid.

To judge the efficacy of this test, assume the elements of the actual sequence have the assumed distribution, but that they are correlated with correlation coefficient p . Determine the probability (as a function of n ) that your test correctly invalidates the preconception.

Is the test based on the sample average optimal? If so, prove it so; if not, find the optimal one.

Delegating Responsibility Modern management styles tend to want decisions to be made locally (by people at the scene) rather than by "the boss." While this approach might be considered more democratic, we should understand how to make decisions under such organizational constraints and what the performance might be. Let three "local" systems separately make observations. Each local system's observations are identically distributed and statistically independent of the others, and based on the observations, each system decides which of two models applies best. The judgments are relayed to the central manager who must make the final decision. Assume the local observations consist either of white Gaussian noise or of a signal having energy E to which the same white Gaussian noise has been added. The signal energy is the same at each local system. Each local decision system must meet a performance standard on the probability it declares the presence of a signal when none is present.

What decision rule should each local system use?

Assuming the observation models are equally likely, how should the central management make its decision so as to minimize the probability of error?

Is this decentralized decision system optimal (i.e., the probability of error for the final decision is minimized)? If so, demonstrate optimality; if not, find the optimal system.

H.L. van Trees Detection, Estimation, and Modulation Theory, Part I John Wiley and Sons 1968 New York T.M. Cover and J.A. Thomas Elements of Information Theory John Wiley and Sons, Inc. 1991