《Mathematics for Computer》Problem Set 10 Solutions

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, 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, 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 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 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 indepen￾dent? 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 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 dur￾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 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’ 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 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 consis￾tent 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 eval￾uate 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)

(c) If you flip a coin 100 times, the probability of flipping exactly 30 heads is approx- imately 23 out of a million. Give an upper bound on the probability of flipping 30 Solution. Applying the bound above gives (23.10-) 100-30+1 100-2.30+1 The actual value is about 39.25. 10-6 Problem 6. Many of the best computer algorithms rely on randomization. However, gen- erating uniform, mutually independent random bits is not so easy!(The mathematician John von Neumann said, " Anyone who considers arithmetic methods of producing ran- dom digits is, of course, in a state of sin. Fortunately, some algorithms work equally well with pairwise-independent random bits, which are relatively"cheap". In particular, one can covert a set of mutually independent bits into an exponentially larger set of pairwise- independent random bits Let b be a set of n uniform mutually-independent o-1 random variables (a) let s be a nonempty subset of the bits in b. let the random variable s be the Xor of all the bits in S. Show that s is uniformly distributed on 0,1] (Hint: Let b be one of the bits in S and let sbe the XoR of all other bits in S. Solution Pr(s=0)=Pr(s=0nb=0)+Pr(s=l0b=1 =Pr(S=0)Pr(b=0)+Pr(s=1)Pr(b=1) 1 Pr(s=0)+Pr( 2(Pr(=0)+Pr(s=1) We first rewrite the events=0 and then use the independence of b and s. The remaining steps use the facts that b is 0 or 1 with equal probability and that sis either 0 or 1(with unknown probabilities). Since s =0 with probability 1/2,we must have s= I with probability 1 2 as well, so s is uniformly distributed on 10,11 (b)Now let T be another nonempty subset of bits in B. Let the random variable t be the XoR of all the bits in T Show that s and t are independent (Hint: Define s to be the Xor of bits in S-t, t' to be the XoR of bits in T-S, and to be the Xor of bits in SnT. Now consider three cases: (1)SnT=0, (2)SnT=S orS∩T=T,and(3)S∩T≠0,S,orT.)

� 6 Problem Set 10 (c) If you flip a coin 100 times, the probability of flipping exactly 30 heads is approx￾imately 23 out of a million. Give an upper bound on the probability of flipping 30 or fewer heads. Solution. Applying the bound above gives: � 23 · 10−6 � 100 − 30 + 1 · 100 − 2 · 30 + 1 ≈ 40 · 10−6 The actual value is about 39.25 · 10−6 . Problem 6. Many of the best computer algorithms rely on randomization. However, gen￾erating uniform, mutually independent random bits is not so easy! (The mathematician John von Neumann said, “Anyone who considers arithmetic methods of producing ran￾dom digits is, of course, in a state of sin.”) Fortunately, some algorithms work equally well with pairwise­independent random bits, which are relatively “cheap”. In particular, one can covert a set of mutually independent bits into an exponentially larger set of pairwise￾independent random bits. Let B be a set of n uniform, mutually­independent 0­1 random variables. (a) Let S be a nonempty subset of the bits in B. Let the random variable s be the XOR of all the bits in S. Show that s is uniformly distributed on {0, 1}. (Hint: Let b be one of the bits in S and let s� be the XOR of all other bits in S.) Solution. Pr (s = 0) = Pr (s� = 0 ∩ b = 0) + Pr (s� = 1 ∩ b = 1) = Pr (s� = 0) Pr (b = 0) + Pr (s� = 1) Pr (b = 1) 1 1 = Pr (s� = 0) + Pr (s� = 1) 2 2 1 = (Pr (s� = 0) + Pr (s� = 1)) 2 1 = 2 We first rewrite the event s = 0 and then use the independence of b and s� . The remaining steps use the facts that b is 0 or 1 with equal probability and that s� is either 0 or 1 (with unknown probabilities). Since s = 0 with probability 1/2, we must have s = 1 with probability 1/2 as well, so s is uniformly distributed on {0, 1}. (b) Now let T be another nonempty subset of bits in B. Let the random variable t be the XOR of all the bits in T. Show that s and t are independent. (Hint: Define s� to be the XOR of bits in S − T, t � to be the XOR of bits in T − S, and i to be the XOR of bits in S ∩ T. Now consider three cases: (1) S ∩ T = ∅, (2) S ∩ T = S or S ∩ T = T, and (3) S ∩ T = ∅, S, or T.)

Problem Set 10 Solution. We must show that Pr(s=ant=b)=Pr(s=a)Pr(t=b)for all a and b By the preceding problem part, Pr(s=a)=Pr(t= b)=1/2. So we really only need to show that for all a and b (s=ant=b)=1/4 Define random variables s t, and i as described above. These random variables are mutually independent since they are functions of mutually independent bits We can rewrite the quantity were trying to analyze, Pr(s =ant=b), in terms of these variables as follows Pr(s=ant=b)=Pr(=ant'=bni=0) +Pr(=a∩t=bni=1) Pr(s=a) Pr(t'=b Pr(i=0) +Pr(s=a)Pr(t'=b Pr(i=1) ow we ar the three cases: 1. If SnT=0, then Pr(i=0)=l and Pr(i=1)=0. However, the sets S-Tand T-Sare nonempty, so Pr(s=a)=Pr(t'=b)=1/2 by the preceding part Substituting into()gives Pr(s=a∩t=b) 1+ 2. If SnT=S, then S-T=0 and so Pr(s'=0)=l and Pr(s'=1)=0. The sets SnT and T-S are nonempty, so i and t' are uniformly distributed by the preceding part. Substituting into ()gives 11 Pr(s=a∩t=b)=0 If SnT=T, then a symmetric argument applies 3. If SnT#0,S, or T, then the sets S-T, T-S, and SnT are all nonempty. Therefore, s, t', and i are all uniformly-distributed. Substituting into()gives 1111111 Pr(s=ant=b) Therefore, s and t are independent (c) Explain how to construct a set of 2n-1 uniform, pairwise-independent 0-1 ran- dom variables from a set of n uniform, mutually-independent 0-1 random variables Solution. Take the sums of all nonempty subsets modulo 2. In the two preceding parts, we proved that these random variables are uniform and pairwise indepen dent (The quantity a1 XOR a2 XOR... XOR an is equal to(a1+a2+..+an)rem 2

� � � � � Problem Set 10 7 Solution. We must show that Pr (s = a ∩ t = b) = Pr (s = a) Pr (t = b) for all a and b. By the preceding problem part, Pr (s = a) = Pr (t = b) = 1/2. So we really only need to show that for all a and b: Pr (s = a ∩ t = b) = 1/4 Define random variables s� , t � , and i as described above. These random variables are mutually independent since they are functions of mutually independent bits. We can rewrite the quantity we’re trying to analyze, Pr (s = a ∩ t = b), in terms of these variables as follows: Pr (s = a ∩ t = b) = Pr (s� = a ∩ t � = b ∩ i = 0) + Pr s� = a ∩ t � = b ∩ i = 1 = Pr (s� = a) Pr (t � = b) Pr (i = 0) + Pr (s� = a) Pr t � = b Pr (i = 1) (*) Now we analyze the three cases: 1. If S ∩T = ∅, then Pr (i = 0) = 1 and Pr (i = 1) = 0. However, the sets S −T and T − S are nonempty, so Pr (s� = a) = Pr (t � = b) = 1/2 by the preceding part. Substituting into (*) gives: 1 1 1 1 1 Pr (s = a ∩ t = b) = 1 + 0 = 2 · 2 · 2 · 2 · 4 2. If S ∩ T = S, then S − T = ∅ and so Pr (s� = 0) = 1 and Pr (s� = 1) = 0. The sets S ∩ T and T − S are nonempty, so i and t � are uniformly distributed by the preceding part. Substituting into (*) gives: 1 1 1 1 1 Pr (s = a ∩ t = b) = 0 · + 1 · = 2 · 2 2 · 2 4 If S ∩ T = T, then a symmetric argument applies. 3. If S ∩ T = ∅, S, or T, then the sets S − T, T − S, and S ∩ T are all nonempty. Therefore, s� , t � , and i are all uniformly­distributed. Substituting into (*) gives: 1 1 1 1 1 1 1 Pr (s = a ∩ t = b) = + = 2 · 2 · 2 2 · 2 · 2 4 Therefore, s and t are independent. (c) Explain how to construct a set of 2n − 1 uniform, pairwise­independent 0­1 ran￾dom variables from a set of n uniform, mutually­independent 0­1 random variables. Solution. Take the sums of all nonempty subsets modulo 2. In the two preceding parts, we proved that these random variables are uniform and pairwise indepen￾dent. (The quantity a1 XOR a2 XOR . . . XOR an is equal to (a1 + a2 + . . . + an) rem 2.)