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?rst 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 de?nition
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 dif?culty is evaluating the sum,We can use the general formula
1
3
1 + 2r + 3r
2
+ 4r +,.,=
(1? r)
2
2 Recitation 21
which is obtained by differentiating the formula for the sum of an in?nite 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
+ 3· + 4· +,.,= =2·
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?rst a,failure” of that child,then the mean time to failure is the expected number
of children after the?rst until the couple has both a boy and a girl,But the probability
of a failure at the kth child after the?rst is 1/2 for all k ≥ 1,So the expected number of
children after the?rst is 1/(1/2) = 2,and the expected number of children including the
rst is 1+2 =3,
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
irt,One student may be in multiple?irting couples; for example,a student in a corner
of the classroom can?irt with up to two others,while a student in the center can?irt
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?irting
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
4 + 3· 4 = 24 pairs of adjacent desks,3·
Number these pairs of adjacent desks from 1 to 24,Let F
i
be an indicator for the event
that occupants of the desks in the i-th pair are?irting,The probability we want is then,
24 24
Ex F
i
= Ex(F
i
)
i=1 i=1
24
= Pr(F
i
= 1)
i=1
The?rst 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?irting if the?rst holds a girl and the second a
111
boy or vice versa,Each of these events happens with probability
,and so the
= ·
42
probability that the occupants?irt is Pr(F
i
= 1) =
11
.
Plugging this into the
+
=
24
2
1
4
Recitation 21 4
previous expression gives,
24
24
Ex F
i
= Pr (F
i
= 1)
i=1 i=1
1
= 24 ·
2
= 12
5 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(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?rst 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
1
6
+ 2
6
+ 3
6
+ 4
6
+ 5
6
+ 6
6
= 7?
6
6
6 Recitation 21
Problem 4,Here are seven propositions,
x
3
x
1
∨ ∨?x
7
x
7
x
5
∨ x
6
∨
x
2
x
6
∨?x
4
∨
x
5
x
4
∨ ∨?x
7
x
3
∨?x
5
∨?x
8
x
9
x
2
∨?x
8
∨
x
4
x
3
∨ x
9
∨
Note that,
1,Each proposition is the OR of three terms of the form x
i
or the form?x
i
,
2,The variables in the three terms in each proposition are all different,
Suppose that we assign true/false values to the variables x
1
,...,x
9
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 T
i
be an indicator for the event that the i-th proposition is true,Then the number
of true propositions is T
1
+,.,+ T
7
and the expected number is,
Ex(T
1
+,.,+ T
7
) = Ex(T
1
) +,.,+ Ex(T
7
)
= 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
T
1
+,..T
7
≥ 6
8
This implies that T
1
+,.,+ T
7
= 7 for at least one outcome,This outcome is an
assignment to the variables such that all of the propositions are true,
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?rst 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 de?nition
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 dif?culty is evaluating the sum,We can use the general formula
1
3
1 + 2r + 3r
2
+ 4r +,.,=
(1? r)
2
2 Recitation 21
which is obtained by differentiating the formula for the sum of an in?nite 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
+ 3· + 4· +,.,= =2·
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?rst a,failure” of that child,then the mean time to failure is the expected number
of children after the?rst until the couple has both a boy and a girl,But the probability
of a failure at the kth child after the?rst is 1/2 for all k ≥ 1,So the expected number of
children after the?rst is 1/(1/2) = 2,and the expected number of children including the
rst is 1+2 =3,
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
irt,One student may be in multiple?irting couples; for example,a student in a corner
of the classroom can?irt with up to two others,while a student in the center can?irt
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?irting
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
4 + 3· 4 = 24 pairs of adjacent desks,3·
Number these pairs of adjacent desks from 1 to 24,Let F
i
be an indicator for the event
that occupants of the desks in the i-th pair are?irting,The probability we want is then,
24 24
Ex F
i
= Ex(F
i
)
i=1 i=1
24
= Pr(F
i
= 1)
i=1
The?rst 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?irting if the?rst holds a girl and the second a
111
boy or vice versa,Each of these events happens with probability
,and so the
= ·
42
probability that the occupants?irt is Pr(F
i
= 1) =
11
.
Plugging this into the
+
=
24
2
1
4
Recitation 21 4
previous expression gives,
24
24
Ex F
i
= Pr (F
i
= 1)
i=1 i=1
1
= 24 ·
2
= 12
5 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(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?rst 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
1
6
+ 2
6
+ 3
6
+ 4
6
+ 5
6
+ 6
6
= 7?
6
6
6 Recitation 21
Problem 4,Here are seven propositions,
x
3
x
1
∨ ∨?x
7
x
7
x
5
∨ x
6
∨
x
2
x
6
∨?x
4
∨
x
5
x
4
∨ ∨?x
7
x
3
∨?x
5
∨?x
8
x
9
x
2
∨?x
8
∨
x
4
x
3
∨ x
9
∨
Note that,
1,Each proposition is the OR of three terms of the form x
i
or the form?x
i
,
2,The variables in the three terms in each proposition are all different,
Suppose that we assign true/false values to the variables x
1
,...,x
9
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 T
i
be an indicator for the event that the i-th proposition is true,Then the number
of true propositions is T
1
+,.,+ T
7
and the expected number is,
Ex(T
1
+,.,+ T
7
) = Ex(T
1
) +,.,+ Ex(T
7
)
= 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
T
1
+,..T
7
≥ 6
8
This implies that T
1
+,.,+ T
7
= 7 for at least one outcome,This outcome is an
assignment to the variables such that all of the propositions are true,
