?
6.042/18.062J Mathematics for Computer Science May 3,2005
Srini Devadas and Eric Lehman
Problem Set 11 Solutions
Due,5PM on Friday,May 6
This is a mini-problem set,The?rst problem reviews basic facts about expectation,
The second and third are typical?nal exam questions,
Problem 1,Answer the following questions about expectation,
(a) There are several equivalent de?nitions of the expectation of a random variable,
If R is a random variable over sample space S,then we can compute Ex (R) by
summing over individual outcomes or by summing over values in the range of R,
Write down these two equivalent de?nitions of Ex (R),
Solution,
Ex (R) = R(w)Pr (w) = v · Pr (R = v)
w∈S v∈ Range(R)
(b) Give another expression for Ex (R)that holds when R is a natural-valued random
variable,
Solution,
∞
Ex (R) = Pr (R > k)
k=0
(c) Give a simple expression for Ex (R) that is valid when R is an indicator random
variable,
Solution,
Ex (R) = Pr (R = 1)
(d) The expectation of a random variable can often be computed from expectations
of simpler random variables,Rewrite each of the expressions below in terms of
Ex (R) and Ex (S),Note any conditions that R and S must satisfy in order for your
equations to hold,Here c is a constant,
Ex (cR) Ex (R + S) Ex (R S)·
?
2 Problem Set 11
Solution,
Ex(cR) = cEx(R)
Ex(R + S) = Ex(R) + Ex(S)
Ex(R · S) = Ex(R) · Ex(S)
The third equation holds only if R and S are independent,
(e) The expected value of a random variable R given that some event E occurs is
denoted Ex(R | E),Write down two equivalent expressions for Ex(R E) based on |
your answers to part (a),
Solution,
Ex(R | E) = R(w)Pr(w | E) = v · Pr(R = v | E)
w∈S v∈ Range(R)
(f) Sometimes the job of computing Ex(R) is best broken down into cases,Let
E
1
,...,E
n
be events that partition the sample space,Suppose you can compute
Ex(R | E
k
) and Pr(E
k
) for all k,How do you then compute Ex(R)?
Solution,
n
Ex(R) = Ex(R | E
k
)Pr(E
k
) (1)
k=1
(g) Many problems involve a sequence of independent trials,each of which succeeds
with probability p,What is the expected number of trials needed to obtain one
success?
Solution,1/p
Problem 2,MIT students sometimes delay laundry for a few days,Assume all random
values described below are mutually independent,
(a) A busy student must complete 3 problem sets before doing laundry,Each prob-
lem set requires 1 day with probability 2/3 and 2 days with probability 1/3,Let B
be the number of days a busy student delays laundry,What is Ex(B)?
Example,If the?rst problem set requires 1 day and the second and third problem
sets each require 2 days,then the student delays for B = 5 days,
Solution,The expected time to complete a problem set is,
2 1 4
+ 2 · =1 ·
3 3 3
Therefore,the expected time to complete all three problem sets is,
Ex(B) = Ex(pset1) + Ex(pset2) + Ex(pset3)
4 4 4
= + +
3 3 3
= 4
3 Problem Set 11
(b) A relaxed student rolls a fair,6-sided die in the morning,If he rolls a 1,then he
does his laundry immediately (with zero days of delay),Otherwise,he delays for
one day and repeats the experiment the following morning,Let R be the number of
days a relaxed student delays laundry,What is Ex(R)?
Example,If the student rolls a 2 the?rst morning,a 5 the second morning,and a 1
the third morning,then he delays for R = 2 days,
Solution,If we regard doing laundry as a failure,then the mean time to failure is
1/(1/6) = 6,However,this counts the day laundry is done,so the number of days
delay is 6? 1 = 5,Alternatively,we could derive the answer as follows,
∞
Ex(R) = Pr(R > k)
k=0
2
3
5 5 5
= + + +,.,
6 6 6
2
5 5 5
= 1 + + +,.,
6
·
6 6
5 1
=
6
·
1? 5/6
= 5
(c) Before doing laundry,an unlucky student must recover from illness for a number
of days equal to the product of the numbers rolled on two fair,6-sided dice,Let U be
the expected number of days an unlucky student delays laundry,What is Ex(U)?
Example,If the rolls are 5 and 3,then the student delays for U = 15 days,
Solution,Let D
1
and D
2
be the two die rolls,Recall that a die roll has expectation
7/2,Thus,
Ex(U) = Ex(D
1
D
2
)·
= Ex(D
1
) · Ex(D
2
)
7 7
=
2
·
2
49
=
4
(d) A student is busy with probability 1/2,relaxed with probability 1/3,and unlucky
with probability 1/6,Let D be the number of days the student delays laundry,What
is Ex(D)?
Solution,
1 1 1
Ex(D) = Ex(B) + Ex(R) + Ex(U)
2 3 6
4
Problem 3,I have twelve cards,
Problem Set 11
1 1 2 2 3 3 4 4 5 5 6 6
I shuf?e them and deal them in a row,For example,I might get,
1 2 3 3 4 6 1 4 5 5 2 6
What is the expected number of adjacent pairs with the same value? In the example,there
are two adjacent pairs with the same value,the 3’s and the 5’s,
Solution,Consider an adjacent pair,The left card matches only one of the other 11
cards,which is equally likely to be in any of the 11 other positions,Therefore,the proba-
bility that an adjacent pair matches is 1/11,Since there are 11 adjacent pairs,the expected
number of matches is 11 · 1/11 = 1 by linearity of expectation,
6.042/18.062J Mathematics for Computer Science May 3,2005
Srini Devadas and Eric Lehman
Problem Set 11 Solutions
Due,5PM on Friday,May 6
This is a mini-problem set,The?rst problem reviews basic facts about expectation,
The second and third are typical?nal exam questions,
Problem 1,Answer the following questions about expectation,
(a) There are several equivalent de?nitions of the expectation of a random variable,
If R is a random variable over sample space S,then we can compute Ex (R) by
summing over individual outcomes or by summing over values in the range of R,
Write down these two equivalent de?nitions of Ex (R),
Solution,
Ex (R) = R(w)Pr (w) = v · Pr (R = v)
w∈S v∈ Range(R)
(b) Give another expression for Ex (R)that holds when R is a natural-valued random
variable,
Solution,
∞
Ex (R) = Pr (R > k)
k=0
(c) Give a simple expression for Ex (R) that is valid when R is an indicator random
variable,
Solution,
Ex (R) = Pr (R = 1)
(d) The expectation of a random variable can often be computed from expectations
of simpler random variables,Rewrite each of the expressions below in terms of
Ex (R) and Ex (S),Note any conditions that R and S must satisfy in order for your
equations to hold,Here c is a constant,
Ex (cR) Ex (R + S) Ex (R S)·
?
2 Problem Set 11
Solution,
Ex(cR) = cEx(R)
Ex(R + S) = Ex(R) + Ex(S)
Ex(R · S) = Ex(R) · Ex(S)
The third equation holds only if R and S are independent,
(e) The expected value of a random variable R given that some event E occurs is
denoted Ex(R | E),Write down two equivalent expressions for Ex(R E) based on |
your answers to part (a),
Solution,
Ex(R | E) = R(w)Pr(w | E) = v · Pr(R = v | E)
w∈S v∈ Range(R)
(f) Sometimes the job of computing Ex(R) is best broken down into cases,Let
E
1
,...,E
n
be events that partition the sample space,Suppose you can compute
Ex(R | E
k
) and Pr(E
k
) for all k,How do you then compute Ex(R)?
Solution,
n
Ex(R) = Ex(R | E
k
)Pr(E
k
) (1)
k=1
(g) Many problems involve a sequence of independent trials,each of which succeeds
with probability p,What is the expected number of trials needed to obtain one
success?
Solution,1/p
Problem 2,MIT students sometimes delay laundry for a few days,Assume all random
values described below are mutually independent,
(a) A busy student must complete 3 problem sets before doing laundry,Each prob-
lem set requires 1 day with probability 2/3 and 2 days with probability 1/3,Let B
be the number of days a busy student delays laundry,What is Ex(B)?
Example,If the?rst problem set requires 1 day and the second and third problem
sets each require 2 days,then the student delays for B = 5 days,
Solution,The expected time to complete a problem set is,
2 1 4
+ 2 · =1 ·
3 3 3
Therefore,the expected time to complete all three problem sets is,
Ex(B) = Ex(pset1) + Ex(pset2) + Ex(pset3)
4 4 4
= + +
3 3 3
= 4
3 Problem Set 11
(b) A relaxed student rolls a fair,6-sided die in the morning,If he rolls a 1,then he
does his laundry immediately (with zero days of delay),Otherwise,he delays for
one day and repeats the experiment the following morning,Let R be the number of
days a relaxed student delays laundry,What is Ex(R)?
Example,If the student rolls a 2 the?rst morning,a 5 the second morning,and a 1
the third morning,then he delays for R = 2 days,
Solution,If we regard doing laundry as a failure,then the mean time to failure is
1/(1/6) = 6,However,this counts the day laundry is done,so the number of days
delay is 6? 1 = 5,Alternatively,we could derive the answer as follows,
∞
Ex(R) = Pr(R > k)
k=0
2
3
5 5 5
= + + +,.,
6 6 6
2
5 5 5
= 1 + + +,.,
6
·
6 6
5 1
=
6
·
1? 5/6
= 5
(c) Before doing laundry,an unlucky student must recover from illness for a number
of days equal to the product of the numbers rolled on two fair,6-sided dice,Let U be
the expected number of days an unlucky student delays laundry,What is Ex(U)?
Example,If the rolls are 5 and 3,then the student delays for U = 15 days,
Solution,Let D
1
and D
2
be the two die rolls,Recall that a die roll has expectation
7/2,Thus,
Ex(U) = Ex(D
1
D
2
)·
= Ex(D
1
) · Ex(D
2
)
7 7
=
2
·
2
49
=
4
(d) A student is busy with probability 1/2,relaxed with probability 1/3,and unlucky
with probability 1/6,Let D be the number of days the student delays laundry,What
is Ex(D)?
Solution,
1 1 1
Ex(D) = Ex(B) + Ex(R) + Ex(U)
2 3 6
4
Problem 3,I have twelve cards,
Problem Set 11
1 1 2 2 3 3 4 4 5 5 6 6
I shuf?e them and deal them in a row,For example,I might get,
1 2 3 3 4 6 1 4 5 5 2 6
What is the expected number of adjacent pairs with the same value? In the example,there
are two adjacent pairs with the same value,the 3’s and the 5’s,
Solution,Consider an adjacent pair,The left card matches only one of the other 11
cards,which is equally likely to be in any of the 11 other positions,Therefore,the proba-
bility that an adjacent pair matches is 1/11,Since there are 11 adjacent pairs,the expected
number of matches is 11 · 1/11 = 1 by linearity of expectation,
