EE178: Homeworks #2 Solutions 1. A new game You have two quarters and a table with a row of squares marked like this: 2 3 4 5 6 7 8 9 10 11 12 Before the game begins, you get to place each quarter on one square. You can put either both quarters on the same square, or you can put them on two different squares: your choice. Then, you roll two fair dice, sum up the numbers showing on the dice to get a number from 2–12, and if there’s a quarter on the square labelled with that number, remove it from the table. (If there are two quarters on that square, remove only one of them.) Now roll the two fair dice a second time, again getting a number from 2–12, and again removing a single quarter from the square with that number, if there’s a quarter there. At this point, the game is over. If you removed both quarters, you win; if any quarter remains on the table, you lose. (a) What’s the probability of winning, if you put two quarters on the square labelled 5? (b) What’s your best strategy? In other words, what’s the best place to put your two quarters, if you want to maximize the probability of winning? State where you should put your two quarters. Then, calculate the probability that you win, if you put your two quarters there. Solution: (a) The sample space is Ω = {((i, j), (k, `)) : 1 ≤ i, j, k, ` ≤ 6}, where i and j denote the numbers on the two dice on the first roll, and k, ` the numbers on the two dice on the second roll. All outcomes are equally likely, so each outcome has probability 1/64 . If we place both quarters on 5, we win if the first roll of both dice sums to 5, and the second roll of both dice sums to 5. Let’s define three events: E = on the first roll of the two dice, they sum to 5 F = on the second roll of the two dice, they sum to 5 Win = we win the game, if we put both our coins on 5 Note that Win = E ∩ F , so our job is to calculate Pr(E ∩ F ). Homework 2 Page 1 of 10 Let’s calculate Pr(E). The outcomes where E occurs are ((1, 4), (k, `)), ((2, 3), (k, `)), ((3, 2), (k, `)), and ((4, 1), (k, `)), where 1 ≤ k, ` ≤ 6. There are 4 × 62 such outcomes. Therefore, 4 × 62 4 Pr(E) = = . 4 6 36 Similarly 4 Pr(F ) = . 36 Now the events E, F are independent. Therefore, Pr(Win) = Pr(E ∩ F ) = Pr(E) × Pr(F ) = 4 4 1 × = . 36 36 81 Alternative approach: Let’s calculate the probability that rolling two fair dice gives us a sum of 5. If we roll two dice, they sum up to 5 if we roll (1, 4), (2, 3), (3, 2), or (4, 1). So, there are 4 ways in which we can roll two dice so that they sum up to 5. Each of these outcomes has probability 1/36, since all 36 outcomes are equally likely. Therefore, the probability of winning if we place both coins on 5 is: 4 1 4 × = . 36 36 81 (b) There are two ways to place the coins if we want to maximize the probability of winning. We can either place the coins on locations 6 and 7, or on locations 7 and 8 (either gives the same chance of winning, and both are optimal). We will calculate the probability that we win by placing the coins on 6 and 7. The sample space is as in part 1. Define the events: Es = on the first roll of the two dice, they sum to s Ft = on the second roll of the two dice, they sum to t Win6,7 = we win the game, if we put our coins on 6 and 7 If we place the coins on locations 6 and 7, we have two ways to win: • We the • We the win if we get a sum of 6 on the first roll of two dice and a sum of 7 on second roll. win if we get a sum of 7 on the first roll of two dice and a sum of 6 on second roll. These two ways are disjoint. In other words, Win6,7 = (E6 ∩ F7 ) ∪ (E7 ∩ F6 ). Let’s calculate the probability of each of these events. There are 6 ways to roll two dice so that they add up to 7. Thus, the probability of getting a 7 in a roll of two dice is 6 1 Pr(E7 ) = Pr(F7 ) = = . 36 6 Homework 2 Page 2 of 10 There are 5 ways to roll two dice so that they add up to 6. Therefore, the probability of getting a 6 if we roll two dice is Pr(E6 ) = Pr(F6 ) = 5 . 36 Moreover, the events Es and Ft are independent for all s, t. It follows that Pr(Win6,7 ) = Pr((E6 ∩ F7 ) ∪ (E7 ∩ F6 )) = Pr(E6 ∩ F7 ) + Pr(E7 ∩ F6 ) = Pr(E6 ) × Pr(F7 ) + Pr(E7 ) × Pr(F6 ) 5 6 6 5 = × + × 36 36 36 36 6 5 =2× × . 36 36 The analysis for placing the coins on locations 7 and 8 is similar, and the probability of winning in that case is the same. Comment: Note that if we place both coins on 7, then we need both rolls of two 6 6 × 36 , which is dice to sum up to 7. The probability of winning in this case is 36 less than the probability of winning if we place the coins on locations 6 and 7 (or on 7 and 8). What happened? It’s tempting to think that the best strategy is to place both coins on 7, since 7 is the most likely sum to get after rolling two dice. However, surprisingly, that isn’t the best possible strategy. In effect, placing the coins on locations 6 and 7 gives us almost twice as many ways to win, which more than compensates for the slight reduction in the probability of rolling a 6 (compared to the probability of rolling a 7). 2. Ternary Channel. The probability transition diagram for a ternary communication channel is shown in the following figure. Assume the input symbols 0, 1, and 2 are sent with probabilities 1/2, 1/4, and 1/4, respectively. Homework 2 Page 3 of 10 (a) Find the probabilities of the output symbols. (b) Given that 1 is received, find the probabilities that the input was 0, 1, or 2. Your answers should be in terms of the conditional error probability . Solution: (a) Let Ai be the event that the input is i and Bi be the event that the output is i. Using the law of total probability and conditional probability we get P(B0 ) = P(B0 | A0 )P(A0 ) + P(B0 | A2 )P(A2 ) = 21 (1 − ) + 14 = 12 − 14 , P(B1 ) = 12 + 14 (1 − ) = 14 + 14 , P(B2 ) = 14 + 14 (1 − ) = 14 . As expected, the sum of the probabilities of the events Bi is 1. (b) The conditional probabilities are P(A0 , B1 ) P(B1 ) 1 2 = 1 1 + 4 (1 − ) 2 P(A0 | B1 ) = = P(A1 | B1 ) = = 2 , 1+ 1 (1−) 4 1 1 + (1−) 2 4 1− , 1+ P(A2 | B1 ) = 0. Again, note that the sum of the conditional probabilities is 1. 3. Independence. You have 2 five-sided dice. The sides of each are numbered from 1 to 5. The dice are “fair”, and each die roll is independent of all others. (a) Event A is “you roll both dice, and the total is 10” (i.e., if you add the number that comes up on one die to the number on the other die, the total is 10). Homework 2 Page 4 of 10 i. Is event A independent of the event “at least one of the dice has a 5 showing”? ii. Is event A independent of the event “at least one of the dice has a 1 showing”? (b) Event B is “you roll both dice and the total is 8”. i. Is event B independent of getting “doubles” (i.e., both dice are showing the same number)? ii. Given that you rolled both dice and the total was 8, what is the probability that at least one of the dice has a 3 showing? iii. Given that you rolled both dice and the total was 8, what is the probability that at least one of the dice has a 5 showing? Solution: (a) The sample space of the experiment of rolling 2 five-sided dice is Ω = {1, 2, 3, 4, 5}× {1, 2, 3, 4, 5} = {1, 2, 3, 4, 5}2 . Overall, there are 25 possible outcomes, which are all equiprobable, since the 2 dice are fair and the rolls are independent of each other. It is useful to define the following events A1 = ”at least one of the dice has a 5 showing” A2 = ”at least one of the dice has a 1 showing” i. It is P(A) = p({5, 5}) = P(A1 ) = 5 X 1 . 25 p({5, j}) + j=1 = 4 X p({i, 5}) i=1 5 4 9 + = . 25 25 25 Moreover, P(A ∩ A1 ) = p({5, 5}) = 1 . 25 We observe that P(A ∩ A1 ) = 9 1 6= 2 = P(A)P(A1 ). 25 25 Thus, the events A and A1 are not independent. ii. It is 5 5 X X 9 P(A2 ) = p({1, j}) + p({i, 1}) = . 25 j=1 i=2 Moreover, 9 = P(A)P(A2 ). 252 So, the events A and A2 are not independent. P(A ∩ A2 ) = p({ø}) = 0 6= Homework 2 Page 5 of 10 (b) Let’s define the events B1 = ”I get doubles” B2 = ”at least one of the dice has a 3 showing” i. It is P(B) = p({4, 4}) + p({3, 5}) + p({5, 3}) = P(B1 ) = 5 X p({i, i}) = i=1 3 . 25 5 . 25 Moreover, P(B ∩ B1 ) = p({4, 4}) = 1 3·5 6= = P(B)P(B1 ). 25 252 Thus, the events B and B1 are not independent. ii. It is 2 P(B ∩ B2 ) = p({3, 5}) + p({5, 3}) = . 25 Thus, we have 2/25 2 P (B ∩ B2 ) = = . P(B2 |B) = P (B) 3/25 3 iii. It is 2 P(B ∩ A1 ) = p({3, 5}) + p({5, 3}) = . 25 So, 2/25 2 P(B ∩ A1 ) = = . P(A1 |B) = P (B) 3/25 3 4. Beat Deep Blue. You’ve been booked to play a chess tournament where to win the tournament, you have to win two consecutive games of chess, out of three games. You have the choice of playing Albert, then Deep Blue, then Albert (ABA)—or Deep Blue, then Albert, then Deep Blue (BAB). Albert is a lousy chess player; Deep Blue is very difficult to beat. Which schedule should you choose, to maximize your chances of winning the tournament? (If you win the first and third game of chess but lose the second, you lose the tournament!) Let’s analyze this puzzle. Suppose you have probability p of beating Deep Blue in any given game, and probability q of beating Albert in any single game. Assume all three games are independent, draws never happen, and 0 < p < q < 1. (a) What is the probability that you win the tournament, if you choose the ABA schedule? (b) What is the probability that you win the tournament, if you choose the BAB schedule? Homework 2 Page 6 of 10 (c) Which schedule offers you the better chances of winning the tournament? Does your answer depend upon the specific values of p, q? Prove your answer. Solution: (a) The sample space is Ω = {LLL, LLW, LW L, LW W, W LL, W LW, W W L, W W W }, where, for instance, LW L indicates that we lose the first game, win the second game, and lose the third game. We can win in three ways: if we win all three games (W W W ), if we win the first and second game and lose the third (W W L), or if we lose the first game and win the second and third game (LW W ). These outcomes have probability qpq, qp(1 − q), and (1 − q)pq, respectively. Thus, the probability of winning on the ABA schedule is: Pr(winning) = qpq + qp(1 − q) + (1 − q)pq = pq(q + 1 − q + 1 − q) = pq(2 − q) (b) The sample space is the same as in part 1, but with a different probability assignment. We can win in the same three ways: win all three games (W W W , with probability pqp), win the first and second game and lose the third (W W L, probability pq(1 − p)), lose the first and win the second and third game (LW W , probability (1 − p)qp). Thus, the probability of winning on the BAB schedule is: Pr(winning) = pqp + pq(1 − p) + (1 − p)qp = pq(p + 1 − p + 1 − p) = pq(2 − p) (c) The BAB schedule offers us a better change of winning. The specific values of p, q don’t matter. The problem statement p < q, from which it follows that 2 − p > 2 − q. Since we know 0 < pq < 1, we can multiply both sides by pq to obtain pq(2 − p) > pq(2 − q). Therefore the probability of winning under the BAB schedule is always strictly larger than the probability of winning under the ABA schedule. Comment: This might seem surprising, because the math tells us to play chesschampion Deep Blue twice and play crummy amateur Albert once, instead of the other way around. Surely it must be better to play the weaker player twice, right? Wrong. If this seems counter-intuitive, here is what is going on. Due to the special victory condition, to win the tournament, you absolutely must win the second game; assuming Homework 2 Page 7 of 10 you do so, you only need to win one out of the other two games. Under the ABA schedule, you have to win your one game against Deep Blue, and you get two chances to beat Albert (you only need to beat him once). Under the BAB schedule, you get two chances to beat Deep Blue (it’s enough to beat Deep Blue once, you don’t have to win both games against Deep Blue), and then you have to win your one game against Albert. Which would you rather have: two chances to beat Deep Blue and just one chance to beat Albert, or two chances to beat Albert and just one chance to beat Deep Blue? It’s better to give yourself as many chances to beat Deep Blue as possible. The trick here is the special rule that to win the tournament you have to win two consecutive games. In comparison, under the standard rule that victory goes to whoever wins any two out of three games, then we get a more intuitive result: you are indeed better off minimizing the number of times you have to play Deep Blue and thus choosing the ABA schedule. 5. Serve on the jury. In the OJ Simpson murder trial, OJ Simpson was accused of murdering his ex-wife, Nicole Simpson. The prosecution introduced evidence showing that OJ had previously abused Nicole. One of Simpson’s defense lawyers, Alan Dershowitz, made the following argument in OJ Simpson’s defense. Dershowitz stated that 1 in 1,000 women abused by their husbands are later killed by their abuser, so the fact that OJ Simpson had previously abused his wife is not relevant and should be disregarded. Assume for this problem that Dershowitz’s 1 in 1,000 statistic is accurate. (a) Are we entitled to conclude that there is only a 1/1000 probability that OJ Simpson murdered Nicole? Why or why not? (b) Suppose we select at random a woman who has been abused by her husband. Define the following events: M is the event that the woman is murdered at some point in her life; G is the event that the woman is murdered by her abuser at some point in her life. A plausible estimate is that 0.2% of abused women will be murdered by someone other than their abuser at some point in their life. Calculate the probability that the selected woman is murdered by her abuser, given that she is murdered. (c) Based upon your answer to part (b), do you agree or disagree with Dershowitz’s argument? Based upon your calculation, would you consider it relevant that OJ Simpson previously abused Nicole? Would you judge it more accurate to use the 1 in 1,000 number or the number you calculated in part (b)? Why? Solution: (a) • Answer 1: No, we are not entitled to conclude that there is a 1/1000 probability that OJ Simpson murdered Nicole. Homework 2 Page 8 of 10 If we define events M and G as in part 2, then the probability that an 1 . However, this abused woman gets murdered by her abuser is Pr(G) = 1000 probability is diluted by the fact that many women are never murdered (by anyone). In this case, we also know that Nicole was murdered. To take into account the fact that we know Nicole was murdered, we should be looking at Pr(G|M ), the probability that a woman is murdered by her abuser given that she is murdered. • Answer 2: No, we are not entitled to conclude that there is a 1/1000 probability that OJ Simpson murdered Nicole. At the trial, the prosecutors produced all sorts of other evidence to support the contention that OJ murdered Nicole; that evidence presumably should increase our estimate of the likelihood that OJ murdered Nicole. Similarly, we should presumably also take into account any evidence introduced by the defense lawyers which indicates that OJ did not murder Nicole; such evidence would presumably reduce our estimate of the likelihood that OJ murdered Nicole. (b) We know from the problem statement that: 1 1000 2 Pr(G ∩ M ) = . 1000 Pr(G) = We need to determine Pr(G|M ). We can calculate it, using the definition of conditional probability: Pr(G ∩ M ) Pr(M ) Pr(G ∩ M ) = Pr(M ∩ G) + Pr(M ∩ G) Pr(G) = Pr(G) + Pr(M ∩ G) Pr(G|M ) = = 1 1000 1 1000 + 2 1000 1 = . 3 Here we have used the fact that G ⊆ M , so G ∩ M = G. In other words, if a woman is murdered by her abuser, she is certainly murdered, so G and M are both true if and only if G is true. In summary, our final answer is Pr(G|M ) = 13 . (c) Dershowitz’s argument is wrong. Based upon our calculations, it is relevant to know that OJ previously abused Nicole. We know that 1 in 1,000 abused women are later killed by their abusers. However, in this case we have the additional Homework 2 Page 9 of 10 information that Nicole was murdered. Out of all murdered abused women, 1 in 3 women are murdered by their abusers. This number is more appropriate to use, because we know that Nicole was murdered. In other words, the conditional probability Pr(G|M ) = 31 better takes into account all of the information available to us, and thus is more appropriate to use in this situation than the unconditional 1 . probability Pr(G) = 1000 Homework 2 Page 10 of 10

© Copyright 2018