CS 70 Discrete Mathematics and Probability Theory
Fall 2017 Kannan Ramchandran and Satish Rao
HW 12
Sundry
Before you start your homework, write down your team. Who else did you work with on this
homework? List na
...
CS 70 Discrete Mathematics and Probability Theory
Fall 2017 Kannan Ramchandran and Satish Rao
HW 12
Sundry
Before you start your homework, write down your team. Who else did you work with on this
homework? List names and email addresses. (In case of homework party, you can also just describe
the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for
your "Sundry" grade.
Please copy the following statement and sign next to it:
I certify that all solutions are entirely in my words and that I have not looked at another student’s
solutions. I have credited all external sources in this write up.
1 Darts with Friends
Michelle and Alex are playing darts. Being the better player, Michelle’s aim follows a uniform
distribution over a circle of radius r around the center. Alex’s aim follows a uniform distribution
over a circle of radius 2r around the center.
(a) Let the distance of Michelle’s throw be denoted by the random variable X and let the distance
of Alex’s throw be denoted by the random variable Y.
• What’s the cumulative distribution function of X?
• What’s the cumulative distribution function of Y?
• What’s the probability density function of X?
• What’s the probability density function of Y?
(b) What’s the probability that Michelle’s throw is closer to the center than Alex’s throw? What’s
the probability that Alex’s throw is closer to the center?
(c) What’s the cumulative distribution function of U = minfX;Yg?
(d) What’s the cumulative distribution function of V = maxfX;Yg?
CS 70, Fall 2017, HW 12 1
(e) What is the expectation of the absolute difference between Michelle’s and Alex’s distances
from the center, that is, what is E[jX -Yj]? [Hint: There are two ways of solving this part.]
2 Variance of the Minimum of Uniform Random Variables
Let n be a positive integer and let X1;:::;Xn i.i.d. ∼ Uniform[0;1]. Find varY, where
Y := minfX1;:::;Xng:
CS 70, Fall 2017, HW 12 4
3 Exponential Practice
Let X ∼ Exponential(lX) and Y ∼ Exponential(lY ) be independent, where lX;lY > 0. Let U =
minfX;Yg, V = maxfX;Yg, and W = V -U.
(a) Compute P(U > t;X ≤ Y), for t ≥ 0.
(b) Use the previous part to compute P(X ≤ Y). Conclude that the events fU > tg and fX ≤ Yg
are independent.
(c) Compute P(W > t j X ≤ Y).
(d) Use the previous part to compute P(W > t).
(e) Calculate P(U > u;W > w), for w > u > 0. Conclude that U and W are independent. [Hint:
Think about the approach you used for the previous parts.]
CS 70, Fall 2017, HW 12 6
4 Exponential Practice II
(a) Let X1;X2 ∼ Exponential(l) be independent, l > 0. Calculate the density of Y := X1 + X2.
[Hint: One way to approach this problem would be to compute the CDF of Y and then differentiate the CDF.]
(b) Let t > 0. What is the density of X1, conditioned on X1 + X2 = t? [Hint: Once again, it may
be helpful to consider the CDF P(X1 ≤ x j X1 + X2 = t). To tackle the conditioning part, try
conditioning instead on the event fX1 +X2 2 [t;t + e]g, where e > 0 is small.]
6 Exponential Approximation to the Geometric Distribution
Say you want to buy your friend a gift for her birthday but it totally slipped your mind and your
friend’s birthday already passed. Well, better late than never, so you order a package from Amazon
which will arrive in X seconds, where X ∼ Geometric(p) (for p 2 (0;1)). The later the package
arrives, the worse it is, so say that the cost of giving your friend the gift is X4, and you wish to
compute E[X4]. Unfortunately, computing E[X4] is very tedious for the geometric distribution, so
approximate X by a suitable exponential distribution and compute E[X4].
To get started on this problem, take a look at P(X > x) for the geometric distribution and the
exponential distribution and note the similarity.
[Note: This problem illustrates that sometimes, moving to the continuous world simplifies calculations!]
[Show More]