《Mathematics for Computer》Notes for Recitation 21

6.042/18.] Mathematics for Computer Science May4,2005 Srini devadas and Eric Lehman Notes for Recitation 21 Problem 1. A couple decides to have children until they have both a boy and a girl. What is the expected number of children that they'll end up with? Assume that each child is equally likely to be a boy or a girl and genders are mutually independent Solution. There are many ways to solve this problem. We'll do it from first principles Suppose that a couple has children until they have both a boy and a girl. a tree dia gram for this experiment is shown below #t kids prob 112 B 112 G 3 1/8 112 1/2 1/2 112 B 112 Let the random variable r be the number of children the couple has. From the definition Ex(R ∑R(m)Pr() 2.-+3·-+4·+ +3·-+4 2(2·+3 The only difficulty is evaluating the sum. We can use the general formula

6.042/18.062J Mathematics for Computer Science May 4, 2005 Srini Devadas and Eric Lehman Notes for Recitation 21 Problem 1. A couple decides to have children until they have both a boy and a girl. What is the expected number of children that they’ll end up with? Assume that each child is equally likely to be a boy or a girl and genders are mutually independent. Solution. There are many ways to solve this problem. We’ll do it from first principles. Suppose that a couple has children until they have both a boy and a girl. A tree dia￾gram for this experiment is shown below. B B B B B G G G G G # kids prob 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 3 2 2 3 1/4 1/8 1/4 1/8 . . . . . . Let the random variable R be the number of children the couple has. From the definition of expectation, we have: � Ex (R) = R(w) · Pr (w) w∈S � � � � 1 1 1 1 1 1 = 2 · � 4 + 3 · 8 + 4 · 16 + . . . + 2 · � 4 + 3 · 8 + 4 · 16 + . . . = 2 2 · 1 4 + 3 · 1 8 + 4 · 1 16 + . . . . (1) The only difficulty is evaluating the sum. We can use the general formula 1 3 1 + 2r + 3r 2 + 4r + . . . = (1 − r)2

Recitation 21 which is obtained by differentiating the formula for the sum of an infinite geometric ries. Setting r= 1/2 gives 1+2 We have to tweak this a little to get the sum were interested in. Subtracting 1 from eacl side and then dividing both sides by 2 does the trick 4×3.1 3 So from (1)we have Ex(R)=2 A much simpler approach uses the fact that the"mean time to failure"is 1/p where p is the probability of failure in one step. If we consider having a child of opposite sex to the first a"failure"of that child, then the mean time to failure is the expected number of children after the first until the couple has both a boy and a girl. But the probability of a failure at the kth child after the first is 1/2 for all k> 1. So the expected number of children after the first is 1/(1/2)=2, and the expected number of children including the first is 1+2

� � Recitation 21 2 which is obtained by differentiating the formula for the sum of an infinite geometric se￾ries. Setting r = 1/2 gives: 1 1 1 1 + 2 · + 3 · + 4 · + . . . = 4 2 4 8 We have to tweak this a little to get the sum we’re interested in. Subtracting 1 from each side and then dividing both sides by 2 does the trick: 1 1 1 4 − 1 3 2 · + 3 · + 4 · + . . . = = 4 8 16 2 2 So from (1) we have 3 Ex (R) = 2 = 3. 2 A much simpler approach uses the fact that the “mean time to failure” is 1/p where p is the probability of failure in one step. If we consider having a child of opposite sex to the first a “failure” of that child, then the mean time to failure is the expected number of children after the first until the couple has both a boy and a girl. But the probability of a failure at the kth child after the first is 1/2 for all k ≥ 1. So the expected number of children after the first is 1/(1/2) = 2, and the expected number of children including the first is 1+2 =3

Recitation 21 Problem 2. A classroom has sixteen desks arranged as shown below If there is a girl in front, behind, to the left, or to the right of a boy, then the two of them flirt. One student may be in multiple flirting couples; for example, a student in a corner of the classroom can flirt with up to two others, while a student in the center can flirt with as many as four others. Suppose that desks are occupied by boys and girls with equal probability and mutually independently. What is the expected number of flirting couples Solution. First, let's count the number of pairs of adjacent desks. There are three in each row and three in each column. Since there are four rows and four columns there are 3·4+3·4=24 pairs of adjacent desks Number these pairs of adjacent desks from 1 to 24. Let Fi be an indicator for the event that occupants of the desks in the i-th pair are flirting. The probability we want is then F)=∑Ex(F) ∑P(F1=1) The first step uses linearity of expectation, and the second uses the fact that the expecata tion of an indicator is equal to the probability that it is 1 The occupants of adjacent desks are flirting if the first holds a girl and the second a boy or vice versa. Each of these events happens with probability 3.2=4 and so the probability that the occupants flirt is Pr(Fi=1)=4+4=2. Plugging this into the

� � � � � Recitation 21 3 Problem 2. A classroom has sixteen desks arranged as shown below. If there is a girl in front, behind, to the left, or to the right of a boy, then the two of them flirt. One student may be in multiple flirting couples; for example, a student in a corner of the classroom can flirt with up to two others, while a student in the center can flirt with as many as four others. Suppose that desks are occupied by boys and girls with equal probability and mutually independently. What is the expected number of flirting couples? Solution. First, let’s count the number of pairs of adjacent desks. There are three in each row and three in each column. Since there are four rows and four columns, there are 3 · 4 + 3 · 4 = 24 pairs of adjacent desks. Number these pairs of adjacent desks from 1 to 24. Let Fi be an indicator for the event that occupants of the desks in the i­th pair are flirting. The probability we want is then: 24 24 Ex Fi = Ex (Fi) i=1 i=1 24 = Pr (Fi = 1) i=1 The first step uses linearity of expectation, and the second uses the fact that the expecata￾tion of an indicator is equal to the probability that it is 1. The occupants of adjacent desks are flirting if the first holds a girl and the second a 11 1 boy or vice versa. Each of these events happens with probability · = , and so the 42 probability that the occupants flirt is Pr (Fi = 1) = 11 + = . Plugging this into the 24 2 1 4

Recitation 21 previous expression gIves F)=∑P(F=1) i=1 i=1 1 24 12

Recitation 21 4 previous expression gives: � � � 24 � 24 Ex Fi = Pr ( Fi = 1) i=1 i=1 1 = 24 · 2 = 12

Recitation 21 Problem 3. There is a nice formula for the expected value of a random variable R that takes on only nonnegative integer values Ex(B)=∑Pr(R>k) Proof ∑P(R>)=P(R=1)+Pr(R=2)+P(R=3)+ +Pr(R=2)+Pr(R=3)+ Pr(r= 3) Pr(R>2) Pr(R=1)+2.Pr(R=2)+3·Pr(R=3)+ Suppose we roll 6 fair, independent dice. Let R be the largest number that comes up Use the formula above to compute Ex(r) Solution. The first task is to compute Pr(r>k); that is, the probability that some die is greater than k. Let's switch to computing the probability of the complementary event Pr(R>k)=1-Pr(R≤k) Now Pr(r 6, then this probability is 1. For smaller k, the probability that one die shows a value in this range is k/ 6. Since the dice are independent, the probability that all 6 dice are in this range is(k /6). Thus, we have Ex(B)=∑Pr(R>k) 、16+26+36+4+56+66

� � � �� � � �� � � �� � � Recitation 21 5 Problem 3. There is a nice formula for the expected value of a random variable R that takes on only nonnegative integer values: ∞ Ex (R) = Pr (R > k) k=0 Proof. ∞ Pr (R > i) = Pr (R = 1) + Pr (R = 2) + Pr (R = 3) + · · · i=0 Pr(R>0) + Pr (R = 2) + Pr (R = 3) + · · · Pr(R>1) + Pr (R = 3) + · · · Pr(R>2) . . . = Pr (R = 1) + 2 · Pr (R = 2) + 3 · Pr (R = 3) + · · · = Ex (R). Suppose we roll 6 fair, independent dice. Let R be the largest number that comes up. Use the formula above to compute Ex (R). Solution. The first task is to compute Pr (R > k); that is, the probability that some die is greater than k. Let’s switch to computing the probability of the complementary event: Pr (R > k) = 1 − Pr (R ≤ k) Now Pr (R ≤ k) is the probability that all the dice show numbers in the set {1, . . . k}. If k ≥ 6, then this probability is 1. For smaller k, the probability that one die shows a value in this range is k/6. Since the dice are independent, the probability that all 6 dice are in this range is (k/6)6. Thus, we have: ∞ Ex (R) = Pr (R > k) k=0 � � �6 � � � � �6 � � � 6 � 1 2 6 = 1 + 1 − 6 + 1 − 6 + . . . + 1 − 6 16 + 26 + 36 + 46 + 56 + 66 = 7 − 66

Recitation 21 Problem 4. Here are seven propositions V t4 V nTA V Ts V.C7 . V.C5 V".C Note that. 1. Each proposition is the OR of three terms of the form m; or the form - i 2. The variables in the three terms in each proposition are all different Suppose that we assign true/false values to the variables J1,..., rg independently and with equal probability (a) What is the expected number of true propositions? Solution. Each proposition is true unless all three of its terms are false. Thus, each proposition is true with probability () Let Ti be an indicator for the event that the i-th proposition is true. Then the number of true propositions is T1+...+T7 and the expected number is Ex(T1+…+T)=Ex(T1)+…+Ex(T7) 7/8+…+7/8 49/8 (b) Use your answer to prove that there exists an assignment to the variables that makes all of the propositions true Solution. A random variable can not always be less than its expectation, so there must be some assignment such that: T1+..T≥6 This implies that T1 +.. T7=7 for at least one outcome. This outcome is an assignment to the variables such that all of the propositions are true

Recitation 21 6 Problem 4. Here are seven propositions: x1 ∨ x3 ∨ ¬x7 ¬x5 ∨ x6 ∨ x7 x2 ∨ ¬x4 ∨ x6 ¬x4 ∨ x5 ∨ ¬x7 x3 ∨ ¬x5 ∨ ¬x8 x9 ∨ ¬x8 ∨ x2 ¬x3 ∨ x9 ∨ x4 Note that: 1. Each proposition is the OR of three terms of the form xi or the form ¬xi. 2. The variables in the three terms in each proposition are all different. Suppose that we assign true/false values to the variables x1, . . . , x9 independently and with equal probability. (a) What is the expected number of true propositions? Solution. Each proposition is true unless all three of its terms are false. Thus, each proposition is true with probability: � �3 1 7 1 − = 2 8 Let Ti be an indicator for the event that the i­th proposition is true. Then the number of true propositions is T1 + . . . + T7 and the expected number is: Ex (T1 + . . . + T7) = Ex (T1) + . . . + Ex (T7) = 7/8 + . . . + 7/8 1 = 49/8 = 6 8 (b) Use your answer to prove that there exists an assignment to the variables that makes all of the propositions true. Solution. A random variable can not always be less than its expectation, so there must be some assignment such that: 1 T1 + . . . T7 ≥ 6 8 This implies that T1 + . . . + T7 = 7 for at least one outcome. This outcome is an assignment to the variables such that all of the propositions are true