Recitation 19 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(the 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, pro- vided p is chosen very carefully. What does your intuition tell you? Solution. Your intuition tells you that a short nap would be nice right now. As would a couple cookies to dunk in a cold glass of milk (b) What is the probability that the experiment succeeds as a function of p and n? Solution. The sample space consists of all possible results of n coin flips, which we can represent by the set (H,Tin. Let e be the event that the experiment successfully selects The One. Then E consists of the n outcomes which contain a single head. In general, the probability of an outcome with h heads and n- h tails is Summing the probabilities of the n outcomes in e gives the probability that the procedure succeeds Pr(E)=mp(1-p)2-1 (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 Solution. We compute the derivative of the success probability d dp n(1-p)-1-np(n-1)(1-p)Recitation 19 5 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 (the 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, pro￾vided p is chosen very carefully. What does your intuition tell you? Solution. Your intuition tells you that a short nap would be nice right now. As would a couple cookies to dunk in a cold glass of milk. (b) What is the probability that the experiment succeeds as a function of p and n? Solution. The sample space consists of all possible results of n coin flips, which we can represent by the set {H, T}n. Let E be the event that the experiment successfully selects The One. Then E consists of the n outcomes which contain a single head. In general, the probability of an outcome with h heads and n − h tails is: hp (1 − p) n−h Summing the probabilities of the n outcomes in E gives the probability that the procedure succeeds: Pr (E) = np(1 − p) n−1 (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!) Solution. We compute the derivative of the success probability: d np(1 − p) n−1 = n(1 − p) n−1 − np(n − 1)(1 − p) n−2 dp