6.042/18.] Mathematics for Computer Science April 26, 2005 Srini devadas and Eric Lehman Problem set 10 Solutions Due: Monday, May 2 at PN Problem 1. Justify your answers to the following questions about independence (a) Suppose that you roll a fair die that has six sides, numbered 1, 2,...,6. Is the event that the number on top is a multiple of 2 independent of the event that the number on top is a multiple of 3? Solution. Let A be the event that the number on top is a multiple of 2, and let b be the event that the number on top is a multiple of 3. We have Pr(A)·Pr(B) 32==P(A∩B) 666 Therefore these events are independent (b) Now suppose that you roll a fair die that has four sides, numbered 1, 2, 3, 4. Is the event that the number on top is a multiple of 2 independent of the event that the number on top is a multiple of 3? Solution. As before, let a be the event that the number on top is a multiple of 2 and let b be the event that the number on top is a multiple of 3. Now, however, we Pr(A) Pr(B But Pr(A∩B)=0 Since these results disagree, the events are not independent (c) Now suppose that you roll a fair die that has eight sides, numbered 1, 2,...,8 Again, is the event that the number on top is a multiple of 2 independent of the event that the number on top is a multiple of 3? Solution. As before, let A be the event that the number on top is a multiple of 2, and let b be the event that the number on top is a multiple of 3. This time, we have Pr(A)·Pr(B) And Pr(A∩B)=1/ Therefore, these events are independent
6.042/18.062J Mathematics for Computer Science April 26, 2005 Srini Devadas and Eric Lehman Problem Set 10 Solutions Due: Monday, May 2 at 9 PM Problem 1. Justify your answers to the following questions about independence. (a) Suppose that you roll a fair die that has six sides, numbered 1, 2, . . ., 6. Is the event that the number on top is a multiple of 2 independent of the event that the number on top is a multiple of 3? Solution. Let A be the event that the number on top is a multiple of 2, and let B be the event that the number on top is a multiple of 3. We have: 3 2 1 Pr (A) · Pr (B) = = = Pr (A ∩ B) 6 · 6 6 Therefore, these events are independent. (b) Now suppose that you roll a fair die that has four sides, numbered 1, 2, 3, 4. Is the event that the number on top is a multiple of 2 independent of the event that the number on top is a multiple of 3? Solution. As before, let A be the event that the number on top is a multiple of 2, and let B be the event that the number on top is a multiple of 3. Now, however, we have: 2 1 1 Pr (A) · Pr (B) = = 4 · 4 8 But: Pr (A ∩ B) = 0 Since these results disagree, the events are not independent. (c) Now suppose that you roll a fair die that has eight sides, numbered 1, 2, . . . , 8. Again, is the event that the number on top is a multiple of 2 independent of the event that the number on top is a multiple of 3? Solution. As before, let A be the event that the number on top is a multiple of 2, and let B be the event that the number on top is a multiple of 3. This time, we have: 4 2 1 Pr (A) · Pr (B) = = 8 · 8 8 And: Pr (A ∩ B) = 1/8 Therefore, these events are independent
Problem Set 10 (d) Finally, suppose that you roll the fair, eight-sided die again. Let the random variable X be the remainder when the number on top is divided by 2, and let the random variable y be the remainder when the number on top is divided by 3. Are the random variables X and Y independent? Solution First, lets tabulate the values of X and y die roll X y 1234567 0101010 1 0 11 Working from the table, we have: 2 r(X=1∩Y=1) But Pr(X=1)·Pr(Y=1) Since these results conflict, the random variables are not independent Problem 2. Philo T Megabrain, a noted parapsychology researcher, has discovered an amazing phenomenon! He puts a psychic on each side of an opaque, soundproof barrier Each psychic rolls a fair die, looks at it, and tries to guess what number came up on the other die by telepathy. Since the dice are fair and independent, the psychics should guess correctly only 1 time in 6. However, after extensive testing, Philo has discovered that they ctually do slightly better (a)Philos somewhat-arbitrary policy is to run the test over and over each day until both psychics roll a 6 at the same time. Then he immediately halts testing for the day, before the psychics make guesses. Explain the flaw in Philos experiment in qualitative terms Solution. If a psychic sees a 6 on her own die, she knows not to guess that the other die is a 6 (b) If a psychic exploits this flaw optimally, with what probabilty can she guess the number on the opposite die?
2 Problem Set 10 (d) Finally, suppose that you roll the fair, eightsided die again. Let the random variable X be the remainder when the number on top is divided by 2, and let the random variable Y be the remainder when the number on top is divided by 3. Are the random variables X and Y independent? Solution. First, let’s tabulate the values of X and Y : die roll X Y 1 1 1 2 0 2 3 1 0 4 0 1 5 1 2 6 0 0 7 1 1 8 0 2 Working from the table, we have: 2 Pr (X = 1 ∩ Y = 1) = 8 But: 4 3 Pr (X = 1) · Pr (Y = 1) = 8 · 8 3 = 16 Since these results conflict, the random variables are not independent. Problem 2. Philo T. Megabrain, a noted parapsychology researcher, has discovered an amazing phenomenon! He puts a psychic on each side of an opaque, soundproof barrier. Each psychic rolls a fair die, looks at it, and tries to guess what number came up on the other die by telepathy. Since the dice are fair and independent, the psychics should guess correctly only 1 time in 6. However, after extensive testing, Philo has discovered that they actually do slightly better. (a) Philo’s somewhatarbitrary policy is to run the test over and over each day until both psychics roll a 6 at the same time. Then he immediately halts testing for the day, before the psychics make guesses. Explain the flaw in Philo’s experiment in qualitative terms. Solution. If a psychic sees a 6 on her own die, she knows not to guess that the other die is a 6. (b) If a psychic exploits this flaw optimally, with what probabilty can she guess the number on the opposite die?
Problem Set 10 Solution. If she sees a 1, 2, 3, 4, or 5, then her probability of guessing the other die is the normal 1 /6. However, if she sees a 6, then she knows that the other die is not a 6, and so her probability of guessing the other die is 1 5. By the total probability law, her probability of guessing the other die correctly in general is 66+65=180 Problem 3. There is a set P consisting of 1000 people The favorite color of 20% of the people is blue The favorite color of 30% is green The favorite color of 50% is red (a)Suppose we select a set of two people Pi, p2) C P uniformly at random. Let the random variables Cl and c denote their favorite colors. are C1 and c2 indepen Solution. No. For example, Pr(C1= blue)=200 /1000. However, Pr(C2=blue C1=blue)=199 /9 since 199 of the remaining 999 people like blue after one person who likes blue is selected (b) Suppose we select a sequence of two people(p1, p2)E Px Uniformly at random Let the random variables Ci and C2 denote their favorite colors. Now are Ci and c2 ndependent? Justify your answer: Solution. Yes. Let c(n) be the color that the n-th person likes. The random vari ables p1 and p2 are independent. Functions of independent random variables are independent, so C1= c(p1) and C2=c(p2)are independent Problem 4. Secret documents are disappearing from CIA headquarters. Some documents are simply misplaced. But the Security Chief suspects that others are begin stolen by Agent X and passed to the government of liechtenstein to further its relentless pursuit of global domination. Two inspectors are assigned to investigate the matter Inspector AM determines that the event that a document disappears during a given day is independent of the event that Agent X is in headquarters that day Similarly, inspector PM determines that the event that a document disappears du ing a given night is independent of the event that Agent X is around that night The Security Chief concludes that the event that a document disappears dent the event that Agent X is present. Therefore, Agent X is probably innocent
Problem Set 10 3 Solution. If she sees a 1, 2, 3, 4, or 5, then her probability of guessing the other die is the normal 1/6. However, if she sees a 6, then she knows that the other die is not a 6, and so her probability of guessing the other die is 1/5. By the total probability law, her probability of guessing the other die correctly in general is: 5 1 1 1 31 + = 6 · 6 6 · 5 180 Problem 3. There is a set P consisting of 1000 people. • The favorite color of 20% of the people is blue. • The favorite color of 30% is green. • The favorite color of 50% is red. (a) Suppose we select a set of two people {p1, p2} ⊆ P uniformly at random. Let the random variables C1 and C2 denote their favorite colors. Are C1 and C2 independent? Justify your answer. Solution. No. For example, Pr (C1 = blue) = 200/1000. However, Pr (C2 = blue | C1 = blue) = 199/999 since 199 of the remaining 999 people like blue after one person who likes blue is selected. (b) Suppose we select a sequence of two people (p1, p2) ∈ P×P uniformly atrandom. Let the random variables C1 and C2 denote their favorite colors. Now are C1 and C2 independent? Justify your answer. Solution. Yes. Let c(n) be the color that the nth person likes. The random variables p1 and p2 are independent. Functions of independent random variables are independent, so C1 = c(p1) and C2 = c(p2) are independent. Problem 4. Secret documents are disappearing from CIA headquarters. Some documents are simply misplaced. But the Security Chief suspects that others are begin stolen by Agent X and passed to the government of Liechtenstein to further its relentless pursuit of global domination. Two inspectors are assigned to investigate the matter: • Inspector AM determines that the event that a document disappears during a given day is independent of the event that Agent X is in headquarters that day. • Similarly, inspector PM determines that the event that a document disappears during a given night is independent of the event that Agent X is around that night. The Security Chief concludes that the event that a document disappears is independent of the event that Agent X is present. Therefore, Agent X is probably innocent
(a) Construct a probability model of the situation. State the inspectors determina tions and the Security Chief's conclusion as probabilities Solution. Let the sample space S be a set of days and nights. Define the following three events D=A secret document disappears X=Agent X is at headquarters A= It is d In these terms Inspector am say Pr(DnX| A)=Pr (D A). Pr(X| A) Inspect Pm says: Pr(DnX| A)=Pr(DI A)- Pr(X|A) And the Security Chief concludes (D∩X)=Pr(D)·Pr(X) (b) Is the Security Chiefs reasoning correct? Justify your answer. Solution. The security chief is wrong. For example, suppose that S consists of a single day and a single night S=day, night) Assign night and day each probability 1/ 2. Now suppose that Agent X is around during the night and a document disappears only at nigl X=night A=(day) Furthe tent with the inspectors'determinations Pr(D∩X|4) Pr(D∩X∩A Pr(a) Pr(D∩A)Pr(X∩A) Pr(D A) Pr(X\A)=Pr(A) Pr(A) Pr(D∩X∩A (DOXIA Pr(D A).Pr(X(=Pr(DnA. Pr(XnA=1
� � � � � � � � � � � � � � 4 Problem Set 10 (a) Construct a probability model of the situation. State the inspectors’ determinations and the Security Chief’s conclusion as probabilities. Solution. Let the sample space S be a set of days and nights. Define the following three events: D = A secret document disappears X = Agent X is at headquarters A = It is daytime. In these terms, Inspector AM says: Pr (D ∩ X A| ) = Pr (D | A) · Pr (X A| ) Inspect PM says: Pr D ∩ X A | = Pr D | A · Pr X | A And the Security Chief concludes: Pr (D ∩ X) = Pr (D) · Pr (X) (b) Is the Security Chief’s reasoning correct? Justify your answer. Solution. The security chief is wrong. For example, suppose that S consists of a single day and a single night: S = {day, night} Assign night and day each probability 1/2. Now suppose that Agent X is around during the night and a document disappears only at night: D = {night} X = {night} A = {day} Furthermore, suppose Pr (day) = Pr (night) = 1/2. These suppositions are consistent with the inspectors’ determinations: Pr (D ∩ X A) = Pr (D ∩ X ∩ A) | = 0 Pr (A) Pr (D | A) · Pr (X A) = Pr (D ∩ A) Pr (X ∩ A) | = 0 Pr (A) · Pr (A) Pr D ∩ X A = Pr D ∩ � X � ∩ A | = 1 Pr A � � � � Pr X ∩ A Pr D | A Pr X | A = Pr D � ∩ � A · � � = 1 Pr A · Pr A
Problem Set 10 However, the Security Chiefs conclusion is wrong because Pr (Dn X)=Pr(night)=1/2 Bu Pr(D)·Pr(X)=(1/2)·(1/2)=1/4 So Agent X may be guilty after all! Problem 5. Suppose you flip n fair, independent coins. Let the random variable X be the number of heads that come up (a) What is the exact value of Pr(X <k), the probability of flipping k or fewer heads? our answer n need not be in closed form Solution (b)Suppose k< n/2. Prove that k+1 Pr(X≤k)≤ Pr(X=k (Upper bound your previous answer with an infinite geometric sum and then eval- uate the sum . Solution. We can upper bound the numerator in the preceding answer as follows k k k k n-k+1(m-k+1)2(n-k+1)3 k+1 k)m-2k+1 (Note that the geometric sum converges only if k n/2.) Therefore k+1 Pr(X≤k) Pr(X=k)
� � � � � � � � � � � � � � � � � � � � � � Problem Set 10 5 However, the Security Chief’s conclusion is wrong, because: Pr (D ∩ X) = Pr (night) = 1/2 But: Pr (D) · Pr (X) = (1/2) · (1/2) = 1/4 So Agent X may be guilty after all! Problem 5. Suppose you flip n fair, independent coins. Let the random variable X be the number of heads that come up. (a) What is the exact value of Pr (X ≤ k), the probability of flipping k orfewer heads? Your answer need not be in closed form. Solution. � � � � � � n n n k k + + −1 . . . + 0 n2 (b) Suppose k < n/2. Prove that: n − k + 1 Pr (X ≤ k) ≤ · Pr (X = k) n − 2k + 1 (Upper bound your previous answer with an infinite geometric sum and then evaluate the sum.) Solution. We can upper bound the numerator in the preceding answer as follows: n n n + + . . . + k k − 1 0 n n = + k n + k(k−1) n + k(k−1)(k−2) + . . . n−k+1 (n−k+1)(n−k+2) (n−k+1)(n−k+2)(n−k+3) k k k k n k k2 k3 ≤ 1 + + + + . . . k · n − k + 1 (n − k + 1)2 (n − k + 1)3 n 1 = k k · 1 − n−k+1 n n − k + 1 = k · n − 2k + 1 (Note that the geometric sum converges only if k < n/2.) Therefore: n − k + 1 Pr (X ≤ k) ≤ n − 2k + 1 · Pr (X = k)