University of California, BerkeleyCOMPSCI 70hw07CS 70 Discrete Mathematics and Probability TheorySummer 2019 James Hulett and Elizabeth Yang Homework 71 Waiting For the BusEdward and Jerry are waiting at the bus stop outside of Soda Hall.Like many bus systems, buses arrive in periodic intervals. However, the Berkeley bus system isunreliable, so the length of these intervals are random, and follow
...[Show More]
hw07
CS 70 Discrete Mathematics and Probability Theory
Summer 2019 James Hulett and Elizabeth Yang Homework 7
1 Waiting For the Bus
Edward and Jerry are waiting at the bus stop outside of Soda Hall.
Like many bus systems, buses arrive in periodic intervals. However, the Berkeley bus system is
unreliable, so the length of these intervals are random, and follow Exponential distributions.
Edward is waiting for the 51B, which arrives according to an Exponential distribution with parameter l. That is, if we let the random variable Xi correspond to the difference between the arrival
time ith and i-1st bus (also known as the inter-arrival time) of the 51B, Xi ∼ Expo(l).
Jerry is waiting for the 79, whose inter-arrival time, follows an Exponential distributions with
parameter m. That is, Yi ∼ Expo(m). Assume that all inter-arrival times are independent.
(a) What is the probability that Jerry’s bus arrives before Edward’s bus?
(b) After 20 minutes, the 79 arrives, and Jerry rides the bus. However, the 51B still hasn’t arrived
yet. Let Let D be the additional amount of time Edward needs to wait for the 51B to arrive.
What is the distribution of D?
(c) Lavanya isn’t picky, so she will wait until either the 51B or the 79 bus arrives. Solve for the
distribution of Z, the amount of time Lavanya will wait before catching the bus.
(d) Khalil arrives at the bus stop, but he doesn’t feel like riding the bus with Edward. He decides
that he will wait for the second arrival of the 51B to ride the bus. Find the distribution of
T = X1 + X2, the amount of time that Khalil will wait to ride the bus. [Hint: One way to
approach this problem would be to compute the CDF of T and then differentiate the CDF.]
2 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.]
3 Normal Darts?
Alex and John are playing a game of darts. Let (Xa;Ya) and (Xj;Yj) denote the coordinates of
Alex’s and John’s darts on the board and are distributed in the following way:
1. Xa;Ya ∼ N(0;1) independently
2. Xj;Yj are distributed uniformly in a circle of radius 3
The winner of the game is determined by whoever’s darts is closer to the center of the board at
(0;0). In this question, we will compute the probability that Alex wins the game. We will denote
the squared distances of the darts from the center by ra = Xa2 +Ya2 and by rj = Xj2 +Yj2.
(a) What is the distribution of ra?
Hint: Consider the joint distribution and the following change of variables formula: Suppose
we want to integrate the function f (x;y) over the circle px2 +y2 ≤ R. Then, we have the
following change of variables formula:
Zpx
2+y2≤R
f (x;y)dxdy = Z0R Z02p f (rcosq;rsinq)rdqdr
You may find the identity sin(q)2 +cos(q)2 = 1 useful.
CS 70, Summer 2019, Homework 7
(b) What is the distribution of rj? (Hint: Try computing the CDF first)
(c) What is the probability that Alex wins the game?
4 The Dwinelle Labyrinth
You have decided to take a humanities class this semester, a French class to be specific. Instead of
a final exam, your professor has issued a final paper. You must turn in this paper before noon to
the professor’s office on floor 3 in Dwinelle, and it’s currently 11:48 a.m.
CS 70, Summer 2019, Homework 7 6
Let Dwinelle be modeled by the following Markov chain. Instead of rushing to turn it in, we will
spend valuable time computing whether or not we could have made it. Suppose walking between
floors takes 1 minute.
(a) Will you make it in time if you choose a floor to transition to uniformly at random? (If Ti is the
number of steps needed to get to F3 starting from Fi, where i 2 f0;1;2;3;4g, is E[T0] < 12?)
(b) Will you make it in time, if for every floor, you order all accessible floors and are twice as likely
to take higher floors? (If you are considering 1, 2, or 3, you will take each with probabilities
1=7, 2=7, 4=7, respectively.)
5 Faulty Machines
You are trying to use a machine that only works on some days. If on a given day the machine is
working, it will break down the next day with probability 0 < b < 1, and works on the next day
1-b. If it is not working on a given day, it will work on the next day with probability 0 < r < 1,
and not work on the next day with probability 1-r. Formulate this process as a Markov chain. As
n ! ¥, what does the probability that on a given day the machine is working converge to? What
properties of the Markov chain allow us to conclude that the probability will actually converge?
6 Three Tails
You flip a fair coin until you see three tails in a row. What is the average number of heads that
you’ll see until getting TTT?
[Show Less]
