《Mathematics for Computer》Problem Set 11 Solutions

6.042/18.] Mathematics for Computer Science May3,2005 Srini devadas and Eric Lehman Problem set 11 Solutions Due: 5PM on Friday, May 6 This is a mini-problem set. The first problem reviews basic facts about expectation. The second and third are typical final exam questions. Problem 1. Answer the following questions about expectation (a) There are several equivalent definitions 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 definitions of Ex(r) Solution Ex(B)=∑()Pr(m) U·Pr(R=) (b) Give another expression for Ex(R)that holds when R is a natural-valued random Solution Ex(B)=∑Pr(R>k) (c) Give a simple expression for Ex( R)that is valid when R is an indicator random ariable (B)=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 (cR) Ex(r+s

� 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 first problem reviews basic facts about expectation. The second and third are typical final exam questions. Problem 1. Answer the following questions about expectation. (a) There are several equivalent definitions 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 definitions 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· )

Problem Set 11 Solution Ex(cr)=cEx(r x(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 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(| E) U·Pr(R=0|E) u∈S v∈ Range(R) (f)Sometimes the job of computing Ex(r)is best broken down into cases. Let El,..., En be events that partition the sample space. Suppose you can compute Ex(R Ek)and Pr(Ek)for all k. How do you then compute Ex(r)? Solution Ex()=∑Bx(R|E)Pr(Ek) (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 Solution. 1/p Problem 2. MIT students sometimes delay laundry for a few days. Assume all random alues 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 first problem set requires l 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 14 herefore, the expected time to complete all three problem sets is Ex(b)=Ex(pset1)+ Ex(pset2)+Ex(pset3

� � � 2 Problem Set 11 Solution. Ex (cR) = c Ex (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 E1, . . . , En be events that partition the sample space. Suppose you can compute Ex (R | Ek) and Pr (Ek) for all k. How do you then compute Ex (R)? Solution. n Ex (R) = Ex (R | Ek) Pr (Ek) (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 first 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 1 · + 2 · = 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

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 first morning, a 5 the second mor 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) 5 6(6 (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 and D2 be the two die rolls. Recall that a die roll has expectation 7/2. Thus Ex(U)=Ex(D1·D2) Ex(D1)·Ex(D2) 77 (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 (D)? Solution (D)=Ex(B)+5Ex(r)+=Ex(U

� Problem Set 11 3 (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 first 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 D1 and D2 be the two die rolls. Recall that a die roll has expectation 7/2. Thus: Ex (U) = Ex (D1 · D2) = Ex (D1) · Ex (D2) 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

Problem Set 11 Problem 3. i have twelve cards 11[212[33445566 I shuffle them and deal them in a row. For example, I might get 1 33461‖145526 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 3s 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 1l 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

4 Problem 3. I have twelve cards: Problem Set 11 1 1 2 2 3 3 4 4 5 5 6 6 I shuffle 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