The radar problem is to guess whether an observed waveform is noise or a signal corrupted by noise. In its simplest form, the signal—which corresponds to the reflection from a target—is deterministic. In the more general setting of a moving target at an unknown distance or velocity, some of the signal's parameters (e.g., delay or phase) are either unknown or random.

Unlike the hypothesis-testing problem that we encountered in Chapter 20, here there is no prior. Consequently, it is meaningless to discuss the probability of error, and a new optimality criterion must be introduced. Typically one wishes to minimize the probability of missed-detection (guessing “no target” in its presence) subject to a constraint on the maximal probability of false alarm (guessing “target” when none is present). More generally, one studies the trade-off between the probability of false alarm and the probability of missed-detection.

There are many other scenarios where one needs to guess in the absence of a prior, e.g., in guessing whether a drug is helpful against some ailment or in guessing whether there is a housing bubble. Consequently, although we shall refer to our problem as “the radar problem,” we shall pose it in greater generality.

The radar problem is closely related to the Knapsack Problem in Computer Science. This relation is explored in Section 30.2.

Readers who prefer to work on their jigsaw puzzle after peeking at the picture on the box should—as recommended—glance at Section 30.11 (without the proofs and referring to Definition 30.5.1 if they must) after reading about the setup and the connection with the Knapsack Problem (Sections 30.1–30.2) and before proceeding to Section 30.3. Others can read in the order in which the results are derived.

The Setup

Two probability density functions f0(・) and f1(・) on the d-dimensional Euclidean space Rd are given. A random vector Y is drawn according to one of them, and our task is to guess according to which. We refer to Y as the observation and to the space Rd, which we denote by Y, as the observation space.