University of California, Berkeley - EECS 126hw11-sol.

Document Content and Description Below

UC Berkeley Department of Electrical Engineering and Computer Sciences EECS 126: Probability and Random Processes Problem Set 11 Spring 2018 Self-Graded Scores Due: 5 PM, Monday April 23, 2018 S... ubmit your self-graded scores via the Google form: https://goo.gl/forms/bT3QsrecePguYHOB3. Make sure you use your SORTABLE NAME on CalCentral. 1. Flipping Coins and Hypothesizing You flip a coin until you see heads. Let X = 0 be the hypothesis that the bias of the coin (the probability of heads) is p, and X = 1 be the hypothesis that the bias of the coin is q, for q > p. Solve the hypothesis testing problem: maximize P[Xˆ = 1 | X = 1] subject to P[Xˆ = 1 | X = 0] ≤ β for β ∈ [0, 1]. Solution: Let Y be the number of flips until we see heads. Write the likelihood ratio. L(y) = P[Y = y | X = 1] P[Y = y | X = 0] = (1 − q) y−1 q (1 − p) y−1p , which is strictly decreasing in y since q > p. Hence, the hypothesis testing rule is of the form Xˆ = 1 if Y < α for some α. Observe that P[Y < α | X = 0] = αX−1 y=1 p(1 − p) y−1 = 1 − (1 − p) α−1 . Therefore, we should choose α such that 1 − (1 − p) α−1 ≤ β, i.e. α ≤ 1 + log(1 − β) log(1 − p) . Therefore, take α = b1 + log(1 − β)/ log(1 − p)c. For the randomization, let P[Xˆ = 1 | Y = α] = γ. The probability of false detection is P[Xˆ = 1 | X = 0] = P[Y < α | X = 0] + γP[Y = α | X = 0] = 1 − (1 − p) α−1 + γp(1 − p) α−1 ≤ β, so we take γ = β − 1 + (1 − p) α−1 p(1 − p) α−1 . 1 Hence, for the values of α and γ described above, Xˆ =    1, Y < α, Z, Y = α, 0, Y > α, where Z is 1 with probability γ and 0 otherwise. 2. BSC Hypothesis Testing Recall that we looked at the MLE and the MAP of the BSC in last week’s homework. Now we will examine the BSC in the hypothesis testing framework. You are testing a digital link that corresponds to a BSC with some error probability  ∈ [0.1, 0.5). You observe n inputs and outputs of the BSC, where n is a positive integer. You want to solve a hypothesis problem to detect that  > 0.1 with a probability of false alarm at most equal to 0.05. Assume that n is very large and use the CLT. Hint: The null hypothesis is  = 0.1. The alternate hypothesis is  > 0.1, which is a composite hypothesis (this means that under the alternate hypothesis, the probability distribution of the observation is not completely determined; compare this to a simple hypothesis such as  = 0.3, which does completely determine the probability distribution of the observation). The NeymanPearson Lemma we learned in class applies for the case of a simple null hypothesis and a simple alternate hypothesis, so it does not directly apply here. To fix this, fix some specific  0 > 0.1 and use the Neyman-Pearson Lemma to find the optimal hypothesis test for the hypotheses  = 0.1 vs.  =  0 . Then, argue that the optimal decision rule does not depend on the specific choice of  0 ; thus, the decision rule you derive will be simultaneously optimal for testing  = 0.1 vs.  =  0 for all  0 > 0.1. Solution: [Show More]

Last updated: 1 year ago

Preview 1 out of 7 pages