4.5 Stein's lemma  (Page 2/2)

In the case that the $L$ observations are statistically independent according to both models, Stein's Lemma states that the false-alarm probabilityresulting from using the Neyman-Pearson hypothesis test has the form (Johnson and Orsak)

Showing this result relies on, believe it or not, the law of large numbers. Define the decision region ${\Re }_1(L)$ according to $${\Re }_1(L)=\{r\colon e^{L((p_{r|{ℳ}_1}, p_{r|{ℳ}_0})-\delta )}\le \frac{p_{r|{ℳ}_1}}{p_{r|{ℳ}_0}}\le e^{L((p_{r|{ℳ}_1}, p_{r|{ℳ}_0})+\delta )}\}$$ This decision region will vary with the number of observations as is typical of Neyman-Pearson decision rules.First of all, we must show that the decision rule this region yields does indeed satisfy a criterion on the miss probability. $$1-P_M=({ℳ}_1, \frac{1}{L}\sum \lg \left(\frac{p(r_l|{ℳ}_1)}{p(r_l|{ℳ}_0)}\right)\in \left((p_{r|{ℳ}_1}, p_{r|{ℳ}_0})-\delta , (p_{r|{ℳ}_1}, p_{r|{ℳ}_0})+\delta \right))$$ This sum is the average of the likelihood ratios computed at each observation assuming that ${ℳ}_1$ is true. Because of the strong law of large numbers, as the number of observations increases, this sum converges toits expected value, which is $(p_{r|{ℳ}_1}, p_{r|{ℳ}_0})$ . Therefore, $\lim_{L\to }L\to$∞ 1 P M 1 for any $\delta$ , which means $P_M\to 0$ . Thus, this decision region guarantees not only that the miss probability is less than some specified number, butalso that it decreases systematically as the number ofobservations increases.

To analyze how the false-alarm probability varies with $L$ , we note that in this decision region $$p_{r|{ℳ}_0}\le p_{r|{ℳ}_1}e^{-(L((p_{r|{ℳ}_1}, p_{r|{ℳ}_0})-\delta ))}$$ $$p_{r|{ℳ}_0}\ge p_{r|{ℳ}_1}e^{-(L((p_{r|{ℳ}_1}, p_{r|{ℳ}_0})+\delta ))}$$ Integrating these over ${\Re }_1(L)$ yields upper and lower bounds on $P_F$ . $$e^{-(L((p_{r|{ℳ}_1}, p_{r|{ℳ}_0})+\delta ))}(1-P_M)\le P_F\le e^{-(L((p_{r|{ℳ}_1}, p_{r|{ℳ}_0})-\delta ))}(1-P_M)$$ or $$-(p_{r|{ℳ}_1}, p_{r|{ℳ}_0})-\delta +\frac{1}{L}\lg (1-P_M)\le \frac{1}{L}\lg P_F\le -(p_{r|{ℳ}_1}, p_{r|{ℳ}_0})+\delta +\frac{1}{L}\lg (1-P_M)$$ Because $\delta$ can be made arbitrarily small as the number of observations increases, we obtain Stein's Lemma.

For the average probability of error, the Chernoff distance is its exponential rate. $$P_e\stackrel{L\to \infty }{\to }f(L)e^{-(L𝒞(p_{r|{ℳ}_1}, p_{r|{ℳ}_0}))}$$ Showing this result leads to more interesting results. For the minimum-probability-of-error detector, the decisionregion ${\Re }_1$ is defined according to ${\pi }_1{p}_{r|{ℳ}_1}> {\pi }_0{p}_{r|{ℳ}_0}$ . Using this fact, we can write the expression for $P_e$ as

The Kullback-Leibler and Chernoff distances are related in an important way. Define $p_s$ to be $\frac{p_0^{(1-s)}{p}_1^s}{J(s)}$ , where $J(s)$ is the normalization constant and the quantity optimized in the definition of the Chernoff distance. TheChernoff distance equals the Kullback-Leibler distance between the $p_s$ equi-distant from $p_0$ and $p_1$ . Call the value of $s$ corresponding to this equi-distant distribution $s^{*}$ ; this value corresponds to the result of the optimization and $$𝒞(p_0, p_1)=(p_{s^{*}}, p_0)=(p_{s^{*}}, p_1)$$ shows that the exponential rates of minimum $P_e$ and Neyman-Pearson hypothesis tests are not necessarily the same. In other words, the distance to theequi-distant distribution need not equal the total distance, which seems to make sense.

The larger the distance, the greater the rate at which the error probability decreases, which corresponds to an easier problem(smaller error probabilities). However, Stein's Lemma does not allow a precise calculation of error probabilities. Thequantity $f(·)$ depends heavily on the underlying probability distributions in ways that are problem dependent. All adistance calculation gives us is the exponential rate.