ECE 561: Detection and Estimation Theory
Spring 2009
Midterm Exam
Issued: March 15th, 2009
March 15, 2009
GENERAL COMMENTS:
You are NOT allowed to collaborate on the midterm problem. Nevertheless,
you are allowed to read/check the Internet for theoretical (mathematical) results
that may help you address the problem. But please refrain from reporting other
people’s work and from trying to track down solutions to the problem online.
You are also allowed to use the text and all the handouts for the class for your
work.
The exam will test your knowledge about the material covered by March
11th, 2009. Some questions ask you to generalize or extend some of the analyt-
ical tools we studied in class, and hence may not have one unique solution, and
there may be many different approaches that one can take to address them.
• 1) Uniformly most powerful tests
Consider the hypothesis testing problem
H0 : Yk = Nk , k = 1, 2,
H1 : Yk = θ sk + Nk , k = 1, 2,
where N1,2 are independent standard Gaussian random variables, and s1 =
1, s2 = −1. The parameter θ is deterministic, but unknown parameter
that takes on only two values, −1 and +1.
– Is there a UMP test for this problem? If so, find its level α. If not,
explain why such a test does not exist.
– Show that an α-level GLRT for this problem is given by:
dGLRT = 1, if |y1 − y2 | ≥ ηα ,
and zero otherwise.
1
– Show that the probability of detection for the GLRT test in the
previous bullet is actually independent on θ. Express the probability
of detection in terms of the parameter ηα .
• 2) Chernoff information and Kulback-Leibler Distance
The Chernoff information for two distributions f0 and f1 is given by
Z
C(f0 , f1 ) = − min ln f1 (y)s f01−s dy
0≤s≤1
For s ∈ [0, 1], define the distribution:
f1 (y)s f0 (y)1−s dy
fs (y) = R .
f1 (x)s f0 (x)1−s dx
Show that the optimizing value of s, s∗ , in the definition of C(f0 , f1 )
satisfies the equation:
D(fs∗ ||f0 ) = D(fs∗ ||f1 ).
Furthermore, show that the optimal value of the Chernoff information
equals to the two KL divergences above.
• 3) Azuma’s Inequality for Martingales
a) Prove the following claim.
Let {Xk }, k = 0, 1, 2, . . . be a martingale sequence, such that almost surely,
one has |Xk − Xk−1 | < ck , where ck ’s are constants. In other words, the
martingale sequence has bounded increments. Then
−t2
P {Xn − X0 ≥ t} ≤ exp Pn .
2 k=1 c2k
Pk
b) Give the Azuma inequality for Xk = i=1 Yi , where the Yi ’s are i.i.d.
symmetric (i.e., variables that have the same probability for m and −m),
integer-valued, bounded random variables. What does this bound assert
about the growth rate of the sum?
Can you use the above described bounds in the analysis of SPRTs?
• 4) (Difficult; Make out of it as much as you can) KL divergence between
Binomial and Poisson distributions
You learned in elementary probability classes that under appropriate con-
ditions on the parameters of the distributions, the Poisson distribution is
2
a good approximation for the Binomial distribution. Try to show that
this can be mathematically expressed as follows: Given a Binomial dis-
tribution Q with parameters p and n, and a Poisson distribution P with
parameter λ = np, it holds that
1 np2
p 1
D(Q||P ) ≤ + + + p2 .
4 3 2 4n
Based on this result, what can you say about the asymptotic performance
of simple detection schemes that try to discriminate between a Poisson
and Binomial distribution? Focus on the Neyman-Pearson test, and the
analysis from Cover+Thomas we did in class.
• 5) Composite hypothesis testing and SPRTs
In class, we discussed the composite hypothesis test for one simple and
one composite hypothesis. We also finished the discussion on sequential
hypothesis testing via Wald’s zero-overshoot theory. How would you gen-
eralize the SPRT for the composite hypothesis scenario described above?
