《Mathematics for Computer》Notes for Recitation 19

6.042/18.] Mathematics for Computer Science April 27, 2005 Srini devadas and Eric Lehman Notes for recitation 19 roblem 1. Suppose that you flip three fair mutually independent coins. Define the fol- lowing events Let A be the event that the first coin is heads Let b be the event that the second coin is heads Let c be the event that the third coin is heads Let d be the event that an even number of coins are heads (a)Are these events pairwise independent? Solution. The sample space consists of eight, equiprobable outcomes [H, T]3=HHH, HHT, HTH, HTT, THH, THT, TTH, TTT) Each sequence of three symbols specifies the outcomes of the three coin tosses The first three events(A, B, and C) are pairwise independent, since they are mu- tually independent. all that remains is to check that each of these is independent D. By symmetry, we need only check just one of the three, say A Pr(A)=号 Pr(D)= Pr(HHT, HTH, THH, TTT)) Pr(AnD)=Pr(HHT, HTH= Therefore, Pr(An D)= Pr (A). Pr(D), and so these events are independent. We conclude that all four events are pairwise independent (b) are these events three-way independent? That is does Pr(X∩Y∩Z)=Pr(X)Pr(Y)Pr(z) always hold when X, Y, and Z are distinct events drawn from the set (A, B, C, D)? Solution. Because the coin tosses are mutually independent, we know Pr(A∩B∩C)=Pr(A)Pr(B)Pr(

6.042/18.062J Mathematics for Computer Science April 27, 2005 Srini Devadas and Eric Lehman Notes for Recitation 19 Problem 1. Suppose that you flip three fair, mutually independent coins. Define the fol￾lowing events: • Let A be the event that the first coin is heads. • Let B be the event that the second coin is heads. • Let C be the event that the third coin is heads. • Let D be the event that an even number of coins are heads. (a) Are these events pairwise independent? Solution. The sample space consists of eight, equiprobable outcomes: {H, T}3 = {HHH, HHT, HT H, HT T, T HH, T HT, T T H, T T T} Each sequence of three symbols specifies the outcomes of the three coin tosses. The first three events (A, B, and C) are pairwise independent, since they are mu￾tually independent. All that remains is to check that each of these is independent of D. By symmetry, we need only check just one of the three, say A: Pr (A) = Pr (D) 1 2 1 = Pr ({HHT, HT H, THH, T T T}) = 1 2 Pr (A ∩ D) = Pr ({HHT, HT H}) = 4 Therefore, Pr (A ∩ D) = Pr (A) · Pr (D), and so these events are independent. We conclude that all four events are pairwise independent. (b) Are these events three­way independent? That is, does Pr (X ∩ Y ∩ Z) = Pr (X) · Pr (Y ) · Pr (Z) always hold when X, Y , and Z are distinct events drawn from the set {A, B, C, D}? Solution. Because the coin tosses are mutually independent, we know: Pr (A ∩ B ∩ C) = Pr (A) · Pr (B) · Pr (C)

Recitation 19 What remains is to check that equality holds for the other subsets of three events LA, B, D,(A, C, D, and (B, C, D]. By symmetry, again, we need only check one, say the first one Pr(A∩B∩D)=Pr({HHT})=k Since this is equal to Pr(A)- Pr(B). Pr(D), these three events are independent We conclude that all four events are three-way independent (c) Are these events mutually independent? Solution. No, because Pr(A∩ BOCOD)≠Pr(A)·Pr(B)·Pr(C)·Pr(D The probability on the left is zero, but the product on the right is equal to 16

� Recitation 19 2 What remains is to check that equality holds for the other subsets of three events: {A, B, D}, {A, C, D}, and {B, C, D}. By symmetry, again, we need only check one, say the first one. Pr (A ∩ B ∩ D) = Pr ({HHT}) = 1 8 Since this is equal to Pr (A) · Pr (B) · Pr (D), these three events are independent. We conclude that all four events are three­way independent. (c) Are these events mutually independent? Solution. No, because: Pr (A ∩ B ∩ C ∩ D) = Pr (A) · Pr (B) · Pr (C) · Pr (D) The probability on the left is zero, but the product on the right is equal to 1 16

Recitation 19 Fact from lecture. If there are N days in a year and m people in a room, then the proba bility that no two people in the room have the same birthday is about Problem 2. Suppose that we create aa national database of dNA profiles. Let's make some simplistic assumptions Each person can be classified into one of 20 billion different"DNA types".(For example, you might be type #13, 646, 572, 661 and the person next to you might be type #2, 785, 466,098 Let t(r)denote the type of person c Each dNa type is equally probable The dna types of Americans are mutually independent (a)a congressman argues that there are only about 250 million americans, so even if a profile for every American were stored in the database, the probability of even one coincidental match would be very small. How many profiles must the database actually contain in order for the probability of at least one coincidental match be bout 1/2 Solution. By the birthday principle, the probability of a match is around half when the number of entries is: √2ln2.20,000000006,511 (b) Person a is arrested for a crime that was committed by person y. At trial, jurors must determine whether x=y. The crime lab says a and y have the same dNA type. The prosecutor argues that the probability that r and y are different people is only 1 in 20 billion. Write the prosecutor's assertion in mathematical notation and explain her error Solution. The prosecutor is asserting that Pr(a and y are different people T(r)=r(y))=2.10- This assertion is at best false and arguably not even a well-formed mathematical statement. Either a and y are the same person or different people, regardless of the DNA types of all the people in the world. Thus, either c and y are the same person in every outcome or they are different people. Consequently, the probability above is either O or 1, but we don t know which The prosecutor's argument sounds confusingly similar to a correct assertion: if c and y are different people, then: Pr(T(x)=T(y))=2·1 The prosecutor can validly argue that either an amazing 1-in-20 billion coincidence involving DNA has occurred or else r and y are the same person On this basis, a jury might conclude that r is almost surely guilty, but there is nothing in our probabilit model to justify that conclusion directl

� Recitation 19 3 Fact from lecture. If there are N days in a year and m people in a room, then the proba￾bility that no two people in the room have the same birthday is about: e−m2/(2N) Problem 2. Suppose that we create a a national database of DNA profiles. Let’s make some simplistic assumptions: • Each person can be classified into one of 20 billion different “DNA types”. (For example, you might be type #13,646,572,661 and the person next to you might be type #2,785,466,098.) Let T(x) denote the type of person x. • Each DNA type is equally probable. • The DNA types of Americans are mutually independent. (a) A congressman argues that there are only about 250 million Americans, so even if a profile for every American were stored in the database, the probability of even one coincidental match would be very small. How many profiles must the database actually contain in order for the probability of at least one coincidental match be about 1/2? Solution. By the birthday principle, the probability of a match is around half when the number of entries is: 2 ln 2 20 · , 000, 000, 000 = 166, 511 (b) Person x is arrested for a crime that was committed by person y. At trial, jurors must determine whether x = y. The crime lab says x and y have the same DNA type. The prosecutor argues that the probability that x and y are different people is only 1 in 20 billion. Write the prosecutor’s assertion in mathematical notation and explain her error. Solution. The prosecutor is asserting that: 10−10 Pr (x and y are different people | T(x) = T(y)) = 2 · This assertion is at best false and arguably not even a well­formed mathematical statement. Either x and y are the same person or different people, regardless of the DNA types of all the people in the world. Thus, either x and y are the same person in every outcome or they are different people. Consequently, the probability above is either 0 or 1, but we don’t know which. The prosecutor’s argument sounds confusingly similar to a correct assertion: if x and y are different people, then: Pr (T(x) = T(y)) = 2 10−10 · The prosecutor can validly argue that either an amazing 1­in­20 billion coincidence involving DNA has occurred or else x and y are the same person. On this basis, a jury might conclude that x is almost surely guilty, but there is nothing in our probability model to justify that conclusion directly

Recitation 19 Problem 3. Suppose there are 100 people in a room. Assume that their birthdays are in dependent and uniformly distributed. As stated in lecture notes, with probability >99% there will be two that have the same birthday. Now suppose you find out the birthdays of all the people in the room except one-call her "Jane"and find all 99 dates to be different (a) What's wrong with the following argument With probability greater than 99%, some pair of people in the room have the same birthday. Since the 99 people we asked all had different birth days, it follows that with probability greater than 99%o Jane has the same birthday as some other person in the room Solution. Here's the problem with the argument: Let A be the event that some two people in the room have the same birthday. Let b be the event that the 99 people we asked all have different birthdays It is true that Pr (A)>0.99(that is indeed the probability spoken about in the lecture notes). However, that is the a priori probability, i. e, assuming all the birthdays are uniform and independent, with no other constraints. The argument above makes the erroneous assumption that event a has probability of at least 99% even once we know that event b holds. But once we know that event b holds the birthdays are case, they are actually quite different as will be computed iqual to Pr(A)(in our (b)What is the actual probability that Jane has the same birthday as some other Solution. Let S be the set of birthdays of the 99 people in the room other than Jane By assumption, SI=99. Let b be the date of Jane's birthday. Since b is uniformly distributed over a set of size 365, and b is independent of all the birthdays in s,we nave Pr(A|B)=Pr(b∈S) 27.1% 365365 where B is the event that the 99 people we asked all have different birthdays

Recitation 19 4 Problem 3. Suppose there are 100 people in a room. Assume that their birthdays are in￾dependent and uniformly distributed. As stated in lecture notes, with probability > 99% there will be two that have the same birthday. Now suppose you find out the birthdays of all the people in the room except one—call her “Jane”—and find all 99 dates to be different. (a) What’s wrong with the following argument: With probability greater than 99%, some pair of people in the room have the same birthday. Since the 99 people we asked all had different birth￾days, it follows that with probability greater than 99% Jane has the same birthday as some other person in the room. Solution. Here’s the problem with the argument: Let A be the event that some two people in the room have the same birthday. Let B be the event that the 99 people we asked all have different birthdays. It is true that Pr (A) > 0.99 (that is indeed the probability spoken about in the lecture notes). However, that is the a priori probability, i.e., assuming all the birthdays are uniform and independent, with no other constraints. The argument above makes the erroneous assumption that event A has probability of at least 99% even once we know that event B holds. But once we know that event B holds, the birthdays are no longer independent. Thus Pr (A | B) is not necessarily equal to Pr (A) (in our case, they are actually quite different, as will be computed in part (b)). (b) What is the actual probability that Jane has the same birthday as some other person in the room? Solution. Let S be the set of birthdays of the 99 people in the room other than Jane. By assumption, |S| = 99. Let b be the date of Jane’s birthday. Since b is uniformly distributed over a set of size 365, and b is independent of all the birthdays in S, we have S 99 Pr (A B) = Pr (b ∈ S) = | | | = 365 365 ≈ 27.1%, where B is the event that the 99 people we asked all have different birthdays

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

Recitation 19 Now we set the right side equal to zero to find the best probability p p(n-1)(1-p) (1-p)=p(n-1) This answer makes sense, since we want the coin to come up heads exactly 1 time In n (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 large? Solution. Setting p=1/n in the formula for the probability that the experiment succeeds gives n In the limit, this tends to 1/e. McLeod is right

� � Recitation 19 6 Now we set the right side equal to zero to find the best probability p: n(1 − p) n−1 = np(n − 1)(1 − p) n−2 (1 − p) = p(n − 1) p = 1/n This answer makes sense, since we want the coin to come up heads exactly 1 time in n. (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 large? Solution. Setting p = 1/n in the formula for the probability that the experiment succeeds gives: 1 n−1 Pr (E) = 1 − n In the limit, this tends to 1/e. McLeod is right