Problem 1(a)(b)(c)Problem 2Problem 3(a)(b)(c)(d)(e)� � � � � � � � � � � � � � � 6.042/18.062J Mathematics for Computer Science April 22, 2005 Srini Devadas and Eric Lehman Notes for Recitation 18 The Law of Total Probability is a handy tool for breaking down the computation of a prob-ability into distinct cases. More precisely, suppose we are interested in the probability of an event E: Pr (E). Suppose also that the random experiment can evolve in two different ways; that is, two different cases X and Xare possible. Suppose also that • it is easy to find the probability of each case: Pr (X) and Pr X , • it easy to find the probability of the event in each case: Pr (E | X) and Pr E X .| Then finding the probability of E is only two multiplications and an addition away. Theorem 1 (Law of Total Probability). Let E and X be events, and 0 < Pr (X) < 1. Then Pr (E) = Pr (X) · Pr (E | X) + Pr X Pr E | X· Proof. Let’s simplify the right-hand side. Pr (E | X) · Pr (X) + Pr E X Pr X| · � � Pr E ∩ X � = Pr (E ∩ X) · Pr (X) + � � Pr � X Pr (X) Pr X · = Pr (E ∩ X) + Pr E ∩ X = Pr (E) The first step uses the definition of conditional probability. On the next-to-last line, we’re adding the probabilities of all outcomes in E and X to the probabilities of all outcomes in E and not in X. Since every outcome in E is either in X or not in X, this is the sum of the probabilities of all outcomes in E, which equals Pr (E). What happens if the experiment can evolve in more than two different ways? That is, what if there are n cases, X1, . . . , Xn, which are mutually exclusive (no two cases can hap-pen simultaneously) and collectively exhaustive (at least one case must happen)? If it is still easy to find the probability of each case and the probability of the event in each case, then again finding Pr (E) is trivial. Theorem 2. Let E be an event and let X1, . . . , Xn be disjoint events whose union exhausts the sample space. Then nPr (E) = Pr (E | Xi) · Pr (Xi) i=1 provided that Pr (Xi) =� 0.� � � � � � � � 2 Recitation 18 Problem 1. There is a rare and deadly disease called Nerditosis which afflicts about 1 per-son in 1000. On symption is a compulsion to refer to everything— fields of study, classes, buildings, etc.— using numbers. It’s horrible. As victims enter their final, downward spiral, they’re awarded a degree from MIT. Two doctors claim that they can diagnose Nerditosis. (a) Doctor X received his degree from Harvard Medical School. He practices at Mas-sachusetts General Hospital and has access to the latest scanners, lab tests, and re-search. Suppose you ask Doctor X whether you have the disease. • If you have Nerditosis, he says “yes” with probability 0.99. • If you don’t have it, he says “no” with probability 0.97. Let D be the event that you have the disease, and let E be the event that the diag-nosis is erroneous. Use the Total Probability Law to compute Pr (E), the probability that Doctor X makes a mistake. Solution. By the Total Probability Law: Pr (E) = Pr (E | D) · Pr (D) + Pr E D Pr D| · = 0.01 · 0.001 + 0.03 · 0.999 = 0.02998 (b) “Doctor” Y received his genuine degree from a fully-accredited university for $49.95 via a special internet offer. He knows that Nerditosis stikes 1 person in 1000, but is a little shakey on how to interpret this. So if you ask him whether you have the disease, he’ll helpfully say “yes” with probability 1 in 1000 regardless of whether you actually do or not. Let D be the event that you have the disease, and let F be the event that the diag-nosis is faulty. Use the Total Probability Law to compute Pr (F ), the probability that Doctor Y made a mistake. Solution. By the Total Probability Law: Pr (F ) = Pr (F D) · Pr (D) + Pr F | D Pr D| · = 0.999 · 0.001 + 0.001 · 0.999 = 0.001998 (c) Which doctor is more reliable? Solution. Doctor X makes more than 15 times as many errors as Doctor Y .� � � � � � 3 Recitation 18 Problem 2. A Barglesnort makes its lair in one of three caves: 123The Barglesnort inhabits cave 1 with probability 1 2, cave 2 with probability 1, and cave 3 4with probability 1 . A rabbit subsequently moves into one of the two unoccupied caves, 4selected with equal probability. With probability 1, the rabbit leaves tracks at the entrance 3to its cave. (Barglesnorts are much too clever to leave tracks.) What is the probability that the Barglesnort lives in cave 3, given that there are no tracks in front of cave 2? Use a tree diagram and the four-step method. Solution. A tree diagram is given below. Let B3 be the event that the Barglesnort inhabits cave 3, and let T2 be the event that there are tracks in front of cave 2. Taking data from the tree diagram, we can compute the desired probability as follows: Pr B3 | T2 = Pr B�3 ∩� T2 Pr T2 1 1 1+ +24 12 12 = 111 − 12 − 24 5 = 21 In the denominator, we apply the formula Pr T2 = 1 − Pr (T2) for convenience. 123133212Bargle’slairRabbit’sholerabbittracks?noyes1/21/21/41/41/21/21/21/21/21/31/31/31/31/31/32/32/32/32/32/32/3prob.1/121/121/61/61/241/121/241/121/241/121/241/12Bargleyesyesyesyesin 3?Tracksat 2?yesyes� � � � � � � � � � � � � � � � 4 Recitation 18 Problem 3. There is a deck of cards on the table. Either John or Mary shuffled it and we have no reason to believe in one case more than the other. Now, John is a well-known cheater with well-known preferences: he always steals the ace of diamonds while shuf-fling. Mary, on the other hand, is a very honest girl: a deck suffled by her is always a full 52-card deck. (a) You pick the topmost card on the deck and you see a queen of hearts. Before you do any calculations: Who is more likely to have shuffled the deck? Explain. Solution. A shuffling by John strictly increases the fraction of non-aces in the deck. Hence, between the two worlds: (1) the world where John has shuffled the deck and (2) the world where Mary has shuffled the deck it is the first world rather than the second one that favors the event of the topmost card being a non-ace. Since we know this event is a fact and the two worlds are otherwise equally likely, we should bet we live in world (1). (b) Now calculate. What is the probability that John has
View Full Document
Unlocking...