In hypothesis testing, as in all other areas of statistical inference, there are two major schools of thought on designing good tests: Bayesian and frequentist (or classical). Consider the simple binary hypothesis testing problem ℋ 0 : x f 0 x ℋ 1 : x f 1 x In the Bayesian setup, the prior probability π i ℋ i of each hypothesis occurring is assumed known. This approach to hypothesis testing is represented by the minimum Bayes risk criterion and the minimum probability of error criterion. In some applications, however, it may not be reasonable to assign an a priori probability to a hypothesis. For example, what is the a priori probability of a supernova occurring in any particular region of the sky? What is the prior probability of being attacked by a ballistic missile? In such cases we need a decision rule that does not depend on making assumptions about the a priori probability of each hypothesis. Here the Neyman-Pearson criterion offers an alternative to the Bayesian framework. The Neyman-Pearson criterion is stated in terms of certain probabilities associated with a particular hypothesis test. The relevant quantities are summarized in . Depending on the setting, different terminology is used. Statistics Signal Processing Probability Name Notation Name Notation P 0 declare ℋ 1 size α false-alarm probability P F P 1 declare ℋ 1 power β detection probability P D

Here P i declare ℋ j dentoes the probability that we declare hypothesis ℋ j to be in effect when ℋ i is actually in effect. The probabilities P 0 declare ℋ 0 and P 1 declare ℋ 0 (sometimes called the miss probability), are equal to 1 P F and 1 P D , respectively. Thus, P F and P D represent the two degrees of freedom in a binary hypothesis test. Note that P F and P D do not involve a priori probabilities of the hypotheses. These two probabilities are related to each other through the decision regions. If R 1 is the decision region for ℋ 1 , we have P F x R 1 f 0 x P D x R 1 f 1 x The densities f i x are nonnegative, so as R 1 shrinks, both probabilities tend to zero. As R 1 expands, both tend to one. The ideal case, where P D 1 and P F 0 , cannot occur unless the distributions do not overlap (i.e., x f 0 x f 1 x 0 ). Therefore, in order to increase P D , we must also increase P F . This represents the fundamental tradeoff in hypothesis testing and detection theory. Consider the simple binary hypothesis test of a scalar measurement x: ℋ 0 : x 0 1 ℋ 1 : x 1 1 Suppose we use a threshold test x ≷ ℋ 0 ℋ 1 γ where γ is a free parameter. Then the false alarm and detection probabilities are P F t γ 1 2 t 2 2 Q γ P D t γ 1 2 t 1 2 2 Q γ 1 where Q denotes the Q-function. These quantities are depicted in .

False alarm and detection values for a certain threshold. Since the Q-function is monotonicaly decreasing, it is evident that both P D and P F decay to zero as γ increases. There is also an explicit relationship P D Q Q P F 1 A common means of displaying this relationship is with a receiver operating characteristic (ROC) curve, which is nothing more than a plot of P D versus P F ().

ROC curve for this example.

The Neyman-Pearson Lemma: A First Look The Neyman-Pearson criterion says that we should construct our decision rule to have maximum probability of detection while not allowing the probability of false alarm to exceed a certain value α. In other words, the optimal detector according to the Neyman-Pearson criterion is the solution to the following constrainted optimization problem:

Neyman-Pearson Criterion P D , such that P F α

The maximization is over all decision rules (equivalently, over all decision regions R 0 , R 1 ). Using different terminology, the Neyman-Pearson criterion selects the most powerful test of size (not exceeding) α. Fortunately, the above optimization problem has an explicit solution. This is given by the celebrated Neyman-Pearson lemma, which we now state. To ease the exposition, our initial statement of this result only applies to continuous random variables, and places a technical condition on the densities. A more general statement is given later in the module. Neyman-Pearson Lemma: initial statement Consider the test ℋ 0 : x f 0 x ℋ 1 : x f 1 x where f i x is a density. Define Λ x f 1 x f 0 x , and assume that Λ x satisfies the condition that for each γ , Λ x takes on the value γ with probability zero under hypothesis ℋ 0 . The solution to the optimization problem in is given by Λ x f 1 x f 0 x ≷ ℋ 0 ℋ 1 η where η is such that P F x x Λ x η f 0 x α If α 0 , then η . The optimal test is unique up to a set of probability zero under ℋ 0 and ℋ 1 . The optimal decision rule is called the likelihood ratio test. Λ x is the likelihood ratio, and η is a threshold. Observe that neither the likelihood ratio nor the threshold depends on the a priori probabilities ℋ i . they depend only on the conditional densities f i and the size constraint α. The threshold can often be solved for as a function of α, as the next example shows.

Continuing with , suppose we wish to design a Neyman-Pearson decision rule with size constraint α. We have Λ x 1 2 x 1 2 2 1 2 x 2 2 x 1 2 By taking the natural logarithm of both sides of the LRT and rarranging terms, the decision rule is not changed, and we obtain x ≷ ℋ 0 ℋ 1 η 1 2 γ Thus, the optimal rule is in fact a thresholding rule like we considered in . The false-alarm probability was seen to be P F Q γ Thus, we may express the value of γ required by the Neyman-Pearson lemma in terms of α: γ Q α

Sufficient Statistics and Monotonic Transformations For hypothesis testing involving multiple or vector-valued data, direct evaluation of the size ( P F ) and power ( P D ) of a Neyman-Pearson decision rule would require integration over multi-dimensional, and potentially complicated decision regions. In many cases, however, this can be avoided by simplifying the LRT to a test of the form t ≷ ℋ 0 ℋ 1 γ where the test statistic t T x is a sufficient statistic for the data. Such a simplified form is arrived at by modifying both sides of the LRT with montonically increasing transformations, and by algebraic simplifications. Since the modifications do not change the decision rule, we may calculate P F and P D in terms of the sufficient statistic. For example, the false-alarm probability may be written P F declare ℋ 1 t t t γ f 0 t where f 0 t denotes the density of t under ℋ 0 . Since t is typically of lower dimension than x, evaluation of P F and P D can be greatly simplified. The key is being able to reduce the LRT to a threshold test involving a sufficient statistic for which we know the distribution.

Common Variances, Uncommon Means Let's design a Neyman-Pearson decision rule of size α for the problem ℋ 0 : x 0 σ 2 I ℋ 1 : x μ 1 σ 2 I where μ 0 , σ 2 0 are known, 0 0 … 0 , 1 1 … 1 are N-dimensional vectors, and I is the N ×N identity matrix. The likelihood ratio is Λ x n 1 N 1 2 σ 2 x n μ 2 2 σ 2 n 1 N 1 2 σ 2 x n 2 2 σ 2 n 1 N x n μ 2 2 σ 2 n 1 N x n 2 2 σ 2 1 2 σ 2 n 1 N 2 x n μ μ 2 1 σ 2 N μ 2 2 μ n 1 N x n To simplify the test further we may apply the natural logarithm and rearrange terms to obtain t n 1 N x n ≷ ℋ 0 ℋ 1 σ 2 μ η N μ 2 γ We have used the assumption μ 0 . If μ 0 , then division by μ is not a monotonically increasing operation, and the inequalities would be reversed. The test statistic t is sufficient for the unknown mean. To set the threshold γ, we write the false-alarm probability (size) as P F t γ t t t γ f 0 t To evaluate P F , we need to know the density of t under ℋ 0 . Fortunately, t is the sum of normal variates, so it is again normally distributed. In particular, we have t A x , where A 1 , so t A 0 A σ 2 I A 0 N σ 2 under ℋ 0 . Therefore, we may write P F in terms of the Q-function as P F Q γ N σ The threshold is thus determined by γ N σ Q α Under ℋ 1 , we have t A 1 A σ 2 I A N μ N σ 2 and so the detection probability (power) is P D t γ Q γ N μ N σ Writing P D as a function of P F , the ROC curve is given by P D Q Q P F N μ σ The quantity N μ σ is called the signal-to-noise ratio. As its name suggests, a larger SNR corresponds to improved performance of the Neyman-Pearson decision rule. In the context of signal processing, the foregoing problem may be viewed as the problem of detecting a constant (DC) signal in additive white Gaussian noise: ℋ 0 : x n w n , n = 1 , … , N ℋ 1 : x n A w n , n = 1 , … , N where A is a known, fixed amplitude, and w n 0 σ 2 . Here A corresponds to the mean μ in the example.

The Neyman-Pearson Lemma: General Case In our initial statement of the Neyman-Pearson Lemma, we assumed that for all η, the set x Λ x η x had probability zero under ℋ 0 . This eliminated many important problems from consideration, including tests of discrete data. In this section we remove this restriction. It is helpful to introduce a more general way of writing decision rules. Let φ be a function of the data x with φ x 0 1 . φ defines the decision rule "declare ℋ 1 with probability φ x ." In other words, upon observing x, we flip a " φ x coin." If it turns up heads, we declare ℋ 1 ; otherwise we declare ℋ 0 . Thus far, we have only considered rules with φ x 0 1 Neyman-Pearson Lemma Consider the hypothesis testing problem ℋ 0 : x f 0 x ℋ 1 : x f 1 x where f 0 and f 1 are both pdfs or both pmfs. Let α 0 1 be the size (false-alarm probability) constraint. The decision rule φ x 1 Λ x η ρ Λ x η 0 Λ x η is the most powerful test of size α, where η and ρ are uniquely determined by requiring P F α . If α 0 , we take η , ρ 0 . This test is unique up to sets of probability zero under ℋ 0 and ℋ 1 . When Λ x η 0 for certain η , we choose η and ρ as follows: Write P F Λ x η ρ Λ x η Choose η such that Λ x η α Λ x η Then choose ρ such that ρ Λ x η α Λ x η

Repetition Code Suppose we have a friend who is trying to transmit a bit (0 or 1) to us over a noisy channel. The channel causes an error in the transmission (that is, the bit is flipped) with probability p, where 0 p 1 2 , and p is known. In order to increase the chance of a successful transmission, our friend sends the same bit N times. Assume the N transmissions are statistically independent. Under these assumptions, the bits you receive are Bernoulli random variables: x n Bernoulli θ . We are faced with the following hypothesis test: ℋ 0 : θ p (0 sent) ℋ 1 : θ 1 p (1 sent) We decide to decode the received sequence x x 1 … x N by designing a Neyman-Pearson rule. The likelihood ratio is Λ x n 1 N 1 p x n p 1 x n n 1 N p x n 1 p 1 x n 1 p k p N k p k 1 p N k 1 p p 2 k N where k n 1 N x n is the number of 1s received. k is a sufficient statistic for θ. The LRT is 1 p p 2 k N ⋛ ℋ 0 ℋ 1 η Taking the natural logarithm of both sides and rearranging, we have k ⋛ ℋ 0 ℋ 1 N 2 1 2 η 1 p p γ The false alarm probability is P F k γ ρ k γ k γ 1 N N k p k 1 p N k ρ N γ p γ 1 p N γ γ and ρ are chosen so that P F α , as described above. The corresponding detection probability is P D k γ ρ k γ k γ 1 N N k 1 p k p N k ρ N γ 1 p γ p N γ

Problems Design a hypothesis testing problem involving continous random variables such that Λ x η 0 for certain values of η. Write down the false-alarm probability as a function of the threshold. Make as general a statement as possible about when the technical condition is satisfied. Consider the scalar hypothesis testing problem ℋ 0 : x f 0 x ℋ 1 : x f 1 x where f i x 1 1 x i 2 , i 0 1

Write down the likelihood ratio test.

Determine the decision regions as a function of η 1 for all η 0 . Draw a representative of each. What are the "critical" values of η? There are five distinct cases.

Compute the size and power ( P F and P D ) in terms of the threshold η 1 and plot the ROC. x 1 1 x 2 x

Suppose we decide to use a simple threshold test x ≷ ℋ 0 ℋ 1 η instead of the Neyman-Pearson rule. Does our performance ℋ 0 suffer much? Plot the ROC for this decision rule on the same graph as for the previous ROC.

Suppose we observe N independent realizations of a Poisson random variable k with intensity parameter λ: f k λ λ k k We must decide which of two intensities is in effect: ℋ 0 : λ λ 0 ℋ 1 : λ λ 1 where λ 0 λ 1 .

Write down the likelihood ratio test.

Simplify the LRT to a test statistic involving only a sufficient statistic. Apply a monotonically increasing transformation to simplify further.

Determine the distribution of the sufficient statistic under both hypotheses. Use the characteristic function to show that a sum of IID Poisson variates is again Poisson distributed.

Derive an expression for the probability of error.

Assuming the two hypotheses are equally likely, and λ 0 5 and λ 1 6 , what is the minimum number N of observations needed to attain a false-alarm probability no greater than 0.01? If you have numerical trouble, try rewriting the log-factorial so as to avoid evaluating the factorial of large integers.

In , suppose p 0.1 . What is the smallest value of N needed to ensure P F 0.01 ? What is P D in this case?