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 = min{X,Y }? CS 70, Fall 2017, HW 12 1 (d) What's the cumulative distribution function of V = max{X,Y }? (e) What is the expectation of the absolute difference between Michelle's and Alex's distances from the center, that is, what is E[|X Y |]? [Hint: There are two ways of solving this part.] 2 Variance of the Minimum of Uniform Random Variables i.i.d. Let n be a positive integer and let X1 , . . . , Xn Uniform[0, 1]. Find varY , where Y := min{X1 , . . . , Xn }. 3 Exponential Practice Let X Exponential(X ) and Y Exponential(Y ) be independent, where X , Y > 0. Let U = min{X,Y }, V = max{X,Y }, 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 {U > t} and {X Y } are independent. (c) Compute P(W > t | 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.] 4 Exponential Practice II (a) Let X1 , X2 Exponential( ) be independent, > 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 | X1 + X2 = t). To tackle the conditioning part, try conditioning instead on the event {X1 + X2 [t,t + ]}, where > 0 is small.] 5 Moments of the Exponential Distribution Let X Exponential( ), where > 0. Show that for all positive integers k, E[X k ] = k!/ k . [Use induction.] CS 70, Fall 2017, HW 12 2 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 (0, 1)). The later the package arrives, the worse it is, so say that the cost of giving your friend the gift is X 4 , and you wish to compute E[X 4 ]. Unfortunately, computing E[X 4 ] is very tedious for the geometric distribution, so approximate X by a suitable exponential distribution and compute E[X 4 ]. 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!] CS 70, Fall 2017, HW 12 3