Problem 1Problem 2(a)(b)(c)Problem 3(a)(b)(c)Problem 4(a)(b)(c)(d)Massachusetts Institute of Technology 6.042J/18.062J, Fall ’05: Mathematics for Computer Science Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised November 23, 2005, 1043 minutes In-Class Problems Week 12, Wed. Problem 1. A Barglesnort makes its lair in one of three caves: 123The Barglesnort inhabits cave 1 with probability 1/2, cave 2 with probability 1/4, and cave 3 with probability 1/4. A rabbit subsequently moves into one of the two unoccupied caves, selected with equal probability. With probability 1/3, the rabbit leaves tracks at the entrance to 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. Problem 2. There is a rare and deadly disease called Nerditosis which afflicts about 1 per-son in 1000. One symptom 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 research. 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. Copyright © 2005, Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld.� � � � � � 2 In-Class Problems Week 12, Wed. Let D be the event that you have the disease, and let E be the event that the diagnosis is erroneous. Use the Total Probability Law to compute Pr {E}, the probability that Doctor X makes a mistake. The Total Probability Law is Pr {A} = Pr {A E} · Pr {E} + Pr| A E Pr E .·(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 diagnosis is faulty. Use the Total Probability Law to compute Pr {F }, the probability that Doctor Y made a mistake. (c) Which doctor is more reliable? Problem 3. Suppose there is a system with n components, and we know from past expe-rience that any particular component will fail in a given year with probability p. That is, letting Fi be the event that the ith component fails within one year, we have Pr {Fi} = p for 1 ≤ i ≤ n. The system will fail if any one of its components fails. What can we say about the probability that the system will fail within one year? Let F be the event that the system fails within one year. Without any additional assump-tions, we can’t get an exact answer for Pr {F }. However, we can give useful upper and lower bounds, namely, p ≤ Pr {F } ≤ np. (1) So for example, if n = 100 and p = 10−5, we conclude that there is at most one chance in 1000 of system failure within a year and at least one chance in 100,000. Let’s model this situation with the sample space S ::= P({1, . . . , n}) of subsets of positive integers ≤ n, where s ∈ S corresponds to the indices of the components which fail within one year. For example, {2, 5} is the outcome that the second and fifth components failed within a year and none of the other components failed. So the outcome that the system did not fail corresponds to the emptyset, ∅. (a) Show that the probability that the system fails could be as small as p by describing appropriate probabilities for the sample points.3 In-Class Problems Week 12, Wed. (b) Show that the probability that the system fails could actually could be as large as np by describing appropriate probabilities for the sample points. (c) Prove the inequality (1). Problem 4. There were n Immortal Warriors born into our world, but in the end there can be only one. The Immortals’ original plan was to stalk the world for centuries, dueling one another with ancient swords in dramatic landscapes until only one survivor remained. However, after a thought-provoking discussion of probabilistic independence, they opt to give the following protocol a try: 1. The Immortals forge a coin that comes up heads with probability p. 2. Each Immortal flips the coin once. 3. If exactly one Immortal flips heads, then he or she is declared The One. Otherwise, the protocol is declared a failure, and they all go back to hacking each other up with swords. (a) One of the Immortals (Kurgan from the Russian steppe) argues that as n grows large, the probability that this protocol succeeds must tend to zero. Another (McLeod from the Scottish highlands) argues that this need not be the case, provided p is chosen very carefully. What does your intuition tell you? (b) What is the probability that the experiment succeeds as a function of p and n? (c) How should p, the bias of the coin, be chosen in order to maximize the probability that the experiment succeeds? (You’re going to have to compute a derivative!) (d) What is the probability of success if p is chosen in this way? What quantity does this approach when n, the number of Immortal Warriors, grows
View Full Document
Unlocking...