6.042/18.] Mathematics for Computer Science May6,2005 Srini devadas and Eric Lehman Notes for recitation 22 1 Conditional Expectation and Total Expectation There are conditional expectations, just as there are conditional probabilities. If R is a random variable and e is an event, then the conditional expectation Ex(r e)is defined bv x(R|E)=∑R(),Pr(m|E) For example, let R be the number that comes up on a roll of a fair die, and let E be the event that the number is even. Let's compute Ex(RI E), the expected value of a die roll, given that the result is even Ex(R|E)=∑R(o)P(E) =1.0+2.-+3·0+4.-+5·0+6 It helps to note that the conditional expectation, Ex(R I E)is simply the expectation of R with respect to the probability measure Preo defined in PSet 10. So it's linear Ex(R1+R2 E)=Ex(R1 E)+Ex(r2 E) Conditional expectation is really useful for breaking down the calculation of an ex- pectation into cases. The breakdown is justified by an analogue to the Total Probability The Theorem 1(Total Expectation). Let E1,..., En be events that partition the sample space and all have nonzero probabilities. If R is a random variable, then Ex(B)=Ex(B|E1)Pr(E1)+…+Ex(B|En)·Pr(En) For example, let R be the number that comes up on a fair die and e be the event that result is even, as before. Then E is the event that the result is odd. So the Total Expectation heorem says Pr(E)+Ex(R E). Pr(E)
� � � 6.042/18.062J Mathematics for Computer Science May 6, 2005 Srini Devadas and Eric Lehman Notes for Recitation 22 1 Conditional Expectation and Total Expectation There are conditional expectations, just as there are conditional probabilities. If R is a random variable and E is an event, then the conditional expectation Ex (R | E) is defined by: � Ex (R | E) = R(w) · Pr (w | E) w∈S For example, let R be the number that comes up on a roll of a fair die, and let E be the event that the number is even. Let’s compute Ex (R | E), the expected value of a die roll, given that the result is even. Ex (R | E) = R(w) · Pr (w | E) w∈{1,...,6} 1 1 1 = 1 · 0 + 2 · + 3 · 0 + 4 · + 5 · 0 + 6 · 3 3 3 = 4 It helps to note that the conditional expectation, Ex (R | E) is simply the expectation of R with respect to the probability measure PrE () defined in PSet 10. So it’s linear: Ex (R1 + R2 | E) = Ex (R1 | E) + Ex (R2 | E). Conditional expectation is really useful for breaking down the calculation of an expectation into cases. The breakdown is justified by an analogue to the Total Probability Theorem: Theorem 1 (Total Expectation). Let E1, . . . , En be events that partition the sample space and all have nonzero probabilities. If R is a random variable, then: Ex (R) = Ex (R | E1) · Pr (E1) + · · · + Ex (R E| n) · Pr (En) For example, let R be the number that comes up on a fair die and E be the event that result is even, as before. Then E is the event that the result is odd. So the Total Expectation theorem says: Ex (R) = Ex (R E)·Pr (E) + Ex R E ·Pr (E) � �� � � ��| � � �� � � ��| � � �� � = 7/2 = 4 = 1/2 = ? = 1/2
Recitation 22 The only quantity here that we don' t already know is Ex(RIE), which is the expected die roll, given that the result is odd. Solving this equation for this unknown, we conclude that Ex(rie=3 To prove the Total Expectation Theorem we begin with a lemma Lemma. Let R be a random variable, e be an event with positive probability, and Ie be the indicator variable for e. then Ex(R·IE) Pr(e Proof. Note that for any outcome, s, in the sample space, Pr({s}∩E)= ∫oi(s)=0 Pr(s)if Ie(s)=1, d Pr(s)nE)=Ie(s Pr(s) Ex(R|E)=∑R(s)P({s}E (ef of Ex(E)) ∑R(s) Pr({s}∩E ( Def of pr(·|E) R(s IE(s)·Pr(s) Pr(e) (by(2) ∑ses(F(s)·Is(s)·Pr(s) Pr(e) Ex(R·IE ( Def of ex(R·IE) Now we prove the Total Expectation Theorem: Proof. Since the Eis partition the sample space, R R·I
� � � � � � Recitation 22 2 The only quantity here that we don’t already know is Ex R | E , which is the expected die roll, given that the result is odd. Solving this equation for this unknown, we conclude that Ex R | E = 3. To prove the Total Expectation Theorem, we begin with a Lemma. Lemma. Let R be a random variable, E be an event with positive probability, and IE be the indicator variable for E. Then Ex (R IE) Ex (R | E) = · (1) Pr (E) Proof. Note that for any outcome, s, in the sample space, 0 if IE(s) = 0, Pr ({s} ∩ E) = Pr (s) if IE(s) = 1, and so Pr ({s} ∩ E) = IE(s) · Pr (s). (2) Now, � Ex (R | E) = s∈S R(s) · Pr ({s} | E) = � s∈S R(s) · Pr ({s} ∩ E) Pr (E) = � s∈S R(s) · IE(s) · Pr (s) Pr (E) � (Def of Ex (· | E)) (Def of Pr (· | E)) (by (2)) = s∈S(R(s) · IE(s)) · Pr (s) Pr (E) = Ex (R · IE) Pr (E) (Def of Ex (R · IE)) Now we prove the Total Expectation Theorem: Proof. Since the Ei’s partition the sample space, R = R IEi · (3) i
Recitation 22 for any random variable, R. So Ex(R)=Ex R·I ∑Ex(R·IB) (linearity of Ex o) ∑Bx(R|E)Pr(E) by(1)
Recitation 22 3 for any random variable, R. So � � � Ex (R) = Ex R · IEi (by (3)) � i = Ex (R · IEi ) (linearity of Ex ()) � i = i Ex (R | Ei) · Pr (Ei) (by (1))
Recitation 22 Problem 1. Final exams in 6.042 are graded according to a rigorous procedure With probability the exam is graded by a recitation instructor with probability, it is graded by a lecturer, and with probability ,, it is accidentally dropped behind the radiator and arbitrarily given a score of 84 Recitation instructors score an exam by scoring each problem individually and then taking th ne sum There are ten true/false questions worth 2 points each. For each, full credit given with probability ,, and no credit is given with probability There are four questions worth 15 points each. For each, the score is deter- mined by rolling two fair dice, summing the results, and adding 3 The single 20 point question is awarded either 12 or 18 points with equal prob- Lecturers score an exam by rolling a fair die twice, multiplying the results, and then adding a general impression"score With probability io, the general impression score is 40 With probability ao, the general impression score With probability io, the general impression score Assume all random choices during the grading process are mutually independent (a)What is the expected score on an exam graded by a recitation instructor? Solution. Let X equal the exam score and C be the event that the exam is graded by a recitation instructor. We want to calculate Ex(X C) By linearity of (conditional) expectation, the expected sum of the problem scores is the sum of the expected problem scores. Therefore, we have Ex(X I C)=10. Ex(T/F score C)+4. Ex(15pt prob score |C)+Ex(20pt prob score I C 7 1 +-0+4·2·+3)+ 12+-·18 =102+4:10+15=70 (b) What is the expected score on an exam graded by a lecturer?
Recitation 22 4 Problem 1. Final exams in 6.042 are graded according to a rigorous procedure: • With probability 4 7 the exam is graded by a recitation instructor, with probability 2 it 7 is graded by a lecturer, and with probability 1 7 , it is accidentally dropped behind the radiator and arbitrarily given a score of 84. • Recitation instructors score an exam by scoring each problem individually and then taking the sum. – There are ten true/false questions worth 2 points each. For each, full credit is given with probability 3 4 , and no credit is given with probability 1 . 4 – There are four questions worth 15 points each. For each, the score is determined by rolling two fair dice, summing the results, and adding 3. – The single 20 point question is awarded either 12 or 18 points with equal probability. • Lecturers score an exam by rolling a fair die twice, multiplying the results, and then adding a “general impression” score. 4 – With probability 10 , the general impression score is 40. 3 – With probability 10 , the general impression score is 50. 3 – With probability 10 , the general impression score is 60. Assume all random choices during the grading process are mutually independent. (a) What is the expected score on an exam graded by a recitation instructor? Solution. Let X equal the exam score and C be the event that the exam is graded by a recitation instructor. We want to calculate Ex (X | C). By linearity of (conditional) expectation, the expected sum of the problem scores is the sum of the expected problem scores. Therefore, we have: Ex (X C| ) = 10 · Ex (T/F score C) + 4 · Ex (15pt prob score | C) + Ex (20pt prob score C) � � | � � � � | 3 1 7 1 1 = 10 · 2 + 0 + 4 · 2 · + 3 + 12 + 18 4 · 4 · 2 2 · 2 · 3 = 10 · + 4 · 10 + 15 = 70 2 (b) What is the expected score on an exam graded by a lecturer?
Recitation 22 Solution. Now we want Ex( C), the expected score a lecturer would give Employing linearity again, we have Ex(x iC)=Ex(product of dice IC) +Ex(general impression C) (because the dice are independent) 50+ 60 (c) What is the expected score on a 6.042 exam? Solution. Let X equal the true exam score. The Total Expectation Theorem implies Ex(X)=Ex(X | C)Pr(C)+Ex(X I C)Pr(c) 4 2 +49 +84 4 40+(-+14)+12=6
� � � � � � | � ¯ � � � � � � � | � � � � Recitation 22 5 Solution. Now we want Ex X ¯ | C , the expected score a lecturer would give. Employing linearity again, we have: Ex X C ¯ = Ex product of dice ¯ | C + Ex general impression | C � �2 7 = (because the dice are independent) 2 4 3 3 + 40 + 50 + 60 10 · 10 · 10 · 49 1 = + 49 = 61 4 4 (c) What is the expected score on a 6.042 exam? Solution. Let X equal the true exam score. The Total Expectation Theorem implies: Ex (X ¯ ¯ ) = Ex (X C) Pr (C) + Ex X | C Pr C 4 49 2 1 = 70 · + + 49 + 84 7 4 · 7 · 7 7 1 = 40 + + 14 + 12 = 69 2 2