MAP/ML Detection and Likelihood-Ratio Threshold Tests

By using (8.40) for each sample value $\overrightarrow {y}$ of $\overrightarrow {Y}$, show that

Defining $\gamma = \left\| \overrightarrow {b}-\overrightarrow {a}\right\| /(2\sigma )$, show that

Show that

Show that, conditional on $X=\overrightarrow {a}$, $\mathrm{LLR}(\overrightarrow {Y}) \sim \mathcal{N}(-2\gamma^{2}, 4\gamma^{2})$. Show that, conditional on $X=\overrightarrow {a}$, $\mathrm{LLR}(\overrightarrow {Y})/2\gamma \sim \mathcal{N}(-\gamma , 1)$.

Show that the first half of (8.44) is valid, i.e., that

By essentially repeating (a)--(e), show that the second half of (8.44) is valid, i.e., that

Let $U = (\overrightarrow {b}-\overrightarrow {a})^{\mathsf{T}}K_{Z}^{-1}\overrightarrow {Y}$. Find $\mathbb {E}\left[ U \mid X=\overrightarrow {a} \right]$ and $\mathbb {E}\left[ U \mid X=\overrightarrow {b} \right]$.

Find the conditional variance of $U$ conditional on $X=\overrightarrow {a}$.

Give the threshold test in terms of the sample value $u$ of $U$, and evaluate $\mathbb {P}\left( e_{\eta } \mid X=\overrightarrow {a} \right)$ and $\mathbb {P}\left( e_{\eta } \mid X=\overrightarrow {b} \right)$ from this and (b). Show that your answer agrees with (8.53).

Explain what happens if $[K_{Z}]$ is singular.

Let $Y$ be a discrete observation rv for a binary detection problem, let $y$ be the observed sample value. Let $v = v(y)$ be a sufficient statistic and let $V$ be the corresponding rv. Show that $\Lambda (y)$ is equal to $\mathsf{p}_{V|X}(v(y) \mid b)/\mathsf{p}_{V|X}(v(y) \mid a)$. In other words, show that the likelihood ratio of a sufficient statistic is the same as the likelihood ratio of the original observation.

Show that this also holds for the ratio of probability densities if $V$ is a continuous rv or random vector.

Show that if $v(y)$ is a sufficient statistic according to condition 1 of Theorem 8.2.8, then

Consider the subspace of events conditional on $V(y) = v$ for a given $v$. Show that for $y$ such that $v(y) = v$,

Explain why this argument is valid whether $Y$ is a discrete or continuous rv and whether $V$ is discrete, continuous or part discrete and part continuous.

Let $Y$ be a discrete observation random vector and let $v(y)$ be a function of the sample values of $Y$. Show that

Using Theorem 8.2.8, show that the above fraction is independent of $X$ if and only if $v(y)$ is a sufficient statistic.

Now assume that $Y$ is a continuous observation random vector, that $v(y)$ is a given function, and that $V = v(Y)$ has a probability density. Define

One can interpret this as a strange kind of probability density on a conditional sample space, but it is more straightforward to regard it simply as a fraction. Show that $v(y)$ is a sufficient statistic if and only if this fraction is independent of $x$.

Suppose the observed sample value $\overrightarrow {y}$ is transformed into $\overrightarrow {v} = [A^{-1}]\overrightarrow {y}$. Explain why $\overrightarrow {v}$ is a sufficient statistic for this detection problem (and thus why MAP detection based on $\overrightarrow {v}$ must yield the same decision as that based on $\overrightarrow {y}$).

Consider the detection problem where $\overrightarrow {V} = [A^{-1}]\overrightarrow {a}+\overrightarrow {W}$ given $X=\overrightarrow {a}$ and $[A^{-1}]\overrightarrow {b}+\overrightarrow {W}$ given $X=\overrightarrow {b}$. Find $\mathrm{LLR}(\overrightarrow {v})$ for a sample value $\overrightarrow {v}$ of $\overrightarrow {V}$. Show that this is the same as the $\mathrm{LLR}$ for a sample value $\overrightarrow {y} = [A]\overrightarrow {v}$ of $\overrightarrow {Y}$.

Find $\mathbb {P}\left( e \mid X=\overrightarrow {a} \right)$ and $\mathbb {P}\left( e \mid X=\overrightarrow {b} \right)$ for the detection problem in (b) by using the results of Example 8.2.4. Show that your answer agrees with (8.53).

Convince yourself from the circular symmetry of the situation that the ML receiver calculates the sample values $v_{0}$ and $v_{1}$ of $V_{0} = Y_{1}^{2}+Y_{2}^{2}$ and $V_{1} = Y_{3}^{2}+Y_{4}^{2}$ and chooses $\hat{x}=0$ if $v_{0} \geq v_{1}$ and chooses $\hat{x}=1$ otherwise.

Find $\mathbb {P}\left( V_{1}>v_{1} \mid X=0 \right)$ as a function of $v_{1}>0$.

Show that

Show that

Show that this is equal to $(1/2)\exp (-a^{2}/(4\sigma^{2}))$.

Explain why this is the probability of error (i.e., why the event $V_{1}>V_{0}$ is independent of $\varphi$), and why $\mathbb {P}\left( e \mid X=0 \right) = \mathbb {P}\left( e \mid X=1 \right)$.

Convince yourself from the circular symmetry of the situation that the ML receiver calculates sample values $v_{0}$ and $v_{1}$ for $V_{0} = Y_{1}^{2}+Y_{2}^{2}$ and $V_{1} = Y_{3}^{2}+Y_{4}^{2}$ and chooses $\hat{x}=0$ if $v_{0}>v_{1}$ and chooses $\hat{x}=1$ otherwise.

Find $f_{V_{0}|X}(v_{0} \mid 0)$ and find $f_{V_{1}|X}(v_{1} \mid 0)$.

Let $W = V_{0}-V_{1}$ and find $f_{W}(w \mid X=0)$.

Show that $\mathbb {P}\left( e \mid X=0 \right) = [2+a^{2}/\sigma^{2})]^{-1}$. Explain why this is also the unconditional probability of an incorrect decision.

Initially, a rather noisy test was developed to find which strain is present for patients with the disease. The output of the test is the sample value $y_{1}$ of a rv $Y_{1}$. Given strain 0 ($X=0$), $Y_{1} = 5+Z_{1}$, and given strain 1 ($X=1$), $Y_{1} = 1+Z_{1}$. The measurement noise $Z_{1}$ is independent of $X$ and is Gaussian, $Z_{1} \sim \mathcal{N}(0, \sigma^{2})$. Give the MAP decision rule, i.e., determine the set of observations $y_{1}$ for which the decision is $\hat{x}=1$. Give $\mathbb {P}\left( e \mid X=0 \right)$ and $\mathbb {P}\left( e \mid X=1 \right)$ in terms of the function $Q(x)$.

A budding medical researcher determines that the test is making too many errors. A new measurement procedure is devised with two observation rvs $Y_{1}$ and $Y_{2}$. $Y_{1}$ is the same as in (a). $Y_{2}$, under hypothesis 0, is given by $Y_{2} = 5+Z_{1}+Z_{2}$, and, under hypothesis 1, is given by $Y_{2} = 1+Z_{1}+Z_{2}$. Assume that $Z_{2}$ is independent of both $Z_{1}$ and $X$, and that $Z_{2} \sim \mathcal{N}(0, \sigma^{2})$. Find the MAP decision rule for $\hat{x}$ in terms of the joint observation $(y_{1}, y_{2})$, and find $\mathbb {P}\left( e \mid X=0 \right)$ and $\mathbb {P}\left( e \mid X=1 \right)$.

Explain in laymen's terms why the medical researcher should learn more about probability.

Now suppose that $Z_{2}$, in (b), is uniformly distributed between $0$ and $1$ rather than being Gaussian. We are still given that $Z_{2}$ is independent of both $Z_{1}$ and $X$. Find the MAP decision rule for $\hat{x}$ in terms of the joint observation $(y_{1}, y_{2})$ and find $\mathbb {P}\left( e \mid X=0 \right)$ and $\mathbb {P}\left( e \mid X=1 \right)$.

Finally, suppose that $Z_{1}$ is also uniformly distributed between $0$ and $1$. Again find the MAP decision rule and error probabilities.

Consider a binary hypothesis testing problem, and denote the hypotheses as $X=1$ and $X=-1$. Let $\overrightarrow {a} = (a_{1}, a_{2}, \ldots , a_{n})^{\mathsf{T}}$ be an arbitrary real $n$-vector and let the observation be a sample value $y$ of the rv $\overrightarrow {Y} = X\overrightarrow {a}+\overrightarrow {Z}$, where $\overrightarrow {Z} \sim \mathcal{N}(0, \sigma^{2}[I_{n}])$ and $[I_{n}]$ is the $n \times n$ identity matrix. Assume that $\overrightarrow {Z}$ and $X$ are independent. Find the ML decision rule and find the probabilities of error $\mathbb {P}\left( e \mid X=0 \right)$ and $\mathbb {P}\left( e \mid X=1 \right)$ in terms of the function $Q(x)$.

Now suppose a third hypothesis, $X=0$, is added to the situation of (a). Again the observation rv is $\overrightarrow {Y} = X\overrightarrow {a}+\overrightarrow {Z}$, but here $X$ can take on values $-1, 0$, or $+1$. Find a one-dimensional sufficient statistic for this problem (i.e., a one-dimensional function of $y$ from which the likelihood ratios

can be calculated).

Find the ML decision rule for the situation in (b) and find the probabilities of error, $\mathbb {P}\left( e \mid X=x \right)$ for $x=-1,0,+1$.

Now suppose that $Z_{1}, \ldots , Z_{n}$ in (a) are IID and each is uniformly distributed over the interval $-2$ to $+2$. Also assume that $\overrightarrow {a} = (1,1,\ldots ,1)^{\mathsf{T}}$. Find the ML decision rule for this situation.

Starting with a successful sale at time $0$, let $S_{i}$ be the arrival time of the $i$th subsequent successful sale. The executive observes $S_{1}, S_{2}, \ldots , S_{n} (n \geq 1)$ and chooses the maximum a posteriori probability hypothesis given this observation. Find the joint probability density $f(S_{1}, S_{2}, \ldots , S_{n}|X=1)$ and $f(S_{1}, \ldots , S_{n}|X=0)$ and give the decision rule.

This is the same as (a) except that the system is in steady state at time $0$ (rather than starting with a successful sale). Find the density of $S_{1}$ (the time of the first arrival after time $0$) conditional on $X=0$ and on $X=1$. What is the decision rule now after observing $S_{1}, \ldots , S_{n}$.

This is the same as (b), except rather than observing $n$ successful sales, the successful sales up to some given time $t$ are observed. Find the probability, under each hypothesis, that the first successful sale occurs in $(s_{1}, s_{1}+\Delta ]$, the second in $(s_{2}, s_{2}+\Delta ], \ldots$, and the last in $(s_{N(t)}, s_{N(t)}+\Delta ]$ (assume $\Delta$ very small). What is the decision rule now?

If $A$ is a union of $k$ intervals, show that $A^{c}$ is a union of at most $k+1$ disjoint intervals. Intervals can be open or closed on each end and can be bounded by $\pm \infty$.

Let $\mathcal{I}$ be the partition of $\mathbb {R}$ created by the intervals of both $A$ and of $A^{c}$. Let $\mathcal{I}_{j}$ be the $j$th interval in this partition. Show that

The expression on the right in (b) is a function of the partition but is otherwise independent of $A$. It corresponds to a test where $Y$ is first quantized to a finite set of intervals, and the MAP test is then applied to this discrete problem. We denote this test as $\mathrm{MAP}(\mathcal{I})$. Let the partition $\mathcal{I}'$ be a refinement of $\mathcal{I}$ in the sense that each interval of $\mathcal{I}'$ is contained in some interval of $\mathcal{I}$. Show that

Show that for any two finite partitions of $\mathbb {R}$ into intervals, there is a third finite partition that is a refinement of each of them.

Consider a sequence $\left\{ A_{j}, j \geq 1\right\}$ (each is a finite union of intervals) that approaches the supremum (over finite unions of intervals) of (8.85). Demonstrate a corresponding sequence of successive refinements of partitions $\left\{ \mathcal{I}_{j}, j \geq 1\right\}$ for which $\mathbb {P}\left(\hat{x}_{\mathrm{MAP}(\mathcal{I}_{j})}(Y) = X\right)$ approaches the same limit.

Note what this exercise has shown so far: if the likelihoods have no PDF or PMF, there is no basis for a MAP test on an individual observation $y$. However, by quantizing the observations sufficiently finely, the quantized MAP rule has an overall probability of being correct that is as close as desired to the optimum over all rules where $A$ is a finite (but arbitrarily large) union of intervals. The arbitrarily fine quantization means that the decisions are arbitrarily close to pointwise decisions, and the use of quantization means that infinitely fine resolution is not required for the observations.

Next suppose the supremum in (8.85) is taken over all measurable sets $A \in \mathbb {R}$. Show that, given any measurable set $A$ and any $\epsilon >0$, there is a finite union of intervals $A'$ such that $\mathbb {P}\left( A \neq A' \mid X=\ell \right) \leq \epsilon$ both for $\ell =0$ and $\ell =1$. Show from this that the supremum in (8.85) is the same whether taken over measurable sets or finite unions of intervals.

Find $f_{Y|X}(y \mid 0)$, $f_{Y|X}(y \mid 1)$ and the likelihood ratio $\Lambda (y)$.

Find the threshold test at $\eta$ for each $\eta$, $0<\eta <\infty$ and evaluate the conditional error probabilities, $q_{0}(\eta )$ and $q_{1}(\eta )$.

Find the error curve $u(\theta )$ and explain carefully how $u(0)$ and $u(1/2)$ are found.

Find a discrete sufficient statistic $v(y)$ for this problem that has three sample values.

Describe a decision rule for which the error probability under each hypothesis is $1/4$. You need not use a randomized rule, but you need to handle the don't-care cases under the threshold test carefully.

Use a power series expansion around $r = 0$ to show that $\gamma_{0}(r) - r\gamma_{0}'(r) = -r^{2}\gamma_{0}''(0)/2 + o(r^{2})$.

Choose $r = n^{-1/3}$ in (9.61) and (9.62). Show that (9.61) can then be rewritten as

Thus $\mathbb {P}\left(e(n) \mid X=0\right)$ approaches $0$ with increasing $n$ exponentially in $n^{1/3}$.

Using the same power series expansion for $r$ in (9.62), show that

Thus $\lim_{n}(1/n)\ln \mathbb {P}\left(e(n) \mid X=1\right) = \gamma_{0}'(0) = \mathbb {E}\left[Z \mid X=0\right]$.

Explain why the bound in (9.62) is exponentially tight given that $\mathbb {P}\left(e(n) \mid X=0\right) \rightarrow 0$ as $n \rightarrow \infty$.

Obtain the risk of a decision rule (which may be randomized).

Let $\Pi$ be a prior probability measure on $\left\{ 1,\ldots ,J\right\}$ with $\Pi (\left\{ j\right\} )=\pi_j$, $j=1,\ldots ,J$. Obtain the Bayes risk of a decision rule.

Obtain a Bayes rule under the prior $\Pi$ in (ii).

Assume that $J=2$, $\pi_1=\pi_2=0.5$, and $f_j(x)=\phi (x-\mu_j)$, where $\phi (x)$ is the Lebesgue density of the standard normal distribution and $\mu_j$, $j=1,2$, are known constants. Obtain the Bayes rule in (iii).

Obtain a minimax rule when $J=2$.