《Mathematics for Computer》Lecture 22 Expected Value II

6.042/18.] Mathematics for Computer Science May5,2005 Srini devadas and Eric Lehman Lecture notes ted value li 1 The Number-Picking game Here is a game that you and i could play that reveals a strange property of expectation First, you think of a probability density function on the natural numbers. Your distri bution can be absolutely anything you like. For example, you might choose a uniform distribution on 1, 2,...,6, like the outcome of a fair die roll. Or you might choose a bi nomial distribution on 0, 1,...,n. You can even give every natural number a non-zero probability, provided that the sum of all probabilities is 1 Next, I pick a random number z according to your distribution. Then, you pick a random number y1 according to the same distribution. If your number is bigger than mine(y1 2), then the game ends. Otherwise, if our numbers are equal or mine is bigger (22 y1), then you pick a new number y2 with the same distribution, and keep picking values y3, y4, etc. until you get a value that is strictly bigger than my number, z. What is the expected number of picks that you must make? Certainly, you always need at least one pick, so the expected number is greater than one. An answer like 2 or 3 sounds reasonable, though one might suspect that the answer depends on the distribution. Let' s find out whether or not this intuition is correct 1.1 Analyzing the Game The number of picks you must make is a natural-valued random variable. And, as weve seen, there is a nice formula for the expectation of a natural-valued random variable Ex(# times you pick)=>Pr(# times you pick>k) Suppose that I've picked my number z, and you have picked k numbers y1, y2, ..., yu There are two possibilities If there is a unique largest number among our picks, then my number is as likely to be it ars. So with probability 1/(+1) my number is larger than all of yours, and you must pick again

� 6.042/18.062J Mathematics for Computer Science May 5, 2005 Srini Devadas and Eric Lehman Lecture Notes Expected Value II 1 The Number­Picking Game Here is a game that you and I could play that reveals a strange property of expectation. First, you think of a probability density function on the natural numbers. Your distri￾bution can be absolutely anything you like. For example, you might choose a uniform distribution on 1, 2, . . . , 6, like the outcome of a fair die roll. Or you might choose a bi￾nomial distribution on 0, 1, . . . , n. You can even give every natural number a non­zero probability, provided that the sum of all probabilities is 1. Next, I pick a random number z according to your distribution. Then, you pick a random number y1 according to the same distribution. If your number is bigger than mine (y1 > z), then the game ends. Otherwise, if our numbers are equal or mine is bigger (z ≥ y1), then you pick a new number y2 with the same distribution, and keep picking values y3, y4, etc. until you get a value that is strictly bigger than my number, z. What is the expected number of picks that you must make? Certainly, you always need at least one pick, so the expected number is greater than one. An answer like 2 or 3 sounds reasonable, though one might suspect that the answer depends on the distribution. Let’s find out whether or not this intuition is correct. 1.1 Analyzing the Game The number of picks you must make is a natural­valued random variable. And, as we’ve seen, there is a nice formula for the expectation of a natural­valued random variable: ∞ Ex (# times you pick) = Pr (# times you pick > k) (1) k=0 Suppose that I’ve picked my number z, and you have picked k numbers y1, y2, . . . , yk. There are two possibilities: • If there is a unique largest number among our picks, then my number is as likely to be it as any one of yours. So with probability 1/(k + 1) my number is larger than all of yours, and you must pick again

Expected Value I Otherwise, there are several numbers tied for largest. My number is as likely to be one of these as any of your numbers, so with probability greater than 1/(k+ 1)you must pick again In both cases, with probability at least 1/(k+1), you need more than k picks to beat me other words Pr(# times you pick>k)≥ k+ This suggests that in order to minimize your rolls, you should chose a distribution such that ties are very rare. For example, you might choose the uniform distribution on (1, 2,..., 10003. In this case, the probability that you need more than k picks to beat me is very close to 1/(k+) for moderate values of k. For example, the probability that you need more than 99 picks is almost exactly 1%. This sounds very promising for you; intuitively, you might expect to win within a reasonable number of picks on average! Unfortunately for intuition, there is a simple proof that the expected number of picks that you need in order to beat me is infinite, regardless of the distribution! Let's plug(2) into(1) Ex(# times you pick) ∑; k+1 This phenomenon can cause all sorts of confusion! For example, suppose you have a communication network where each packet of data has a 1/k chance of being delayed by k or more steps. This sounds good; there is only a 1% chance of being delayed by 100 or more steps. But the expected delay for the packet is actually infinite e, There is a larger point here as well: not every random variable has a well-defined expectation. This idea may be disturbing at first, but remember that an expected value is just a weighted average. And there are many sets of numbers that have no conventional average either, such as {1,-2,3,-4,5,-6,…} Strictly speaking, we should qualify virtually all theorems involving expectation with phrases such as".Provided all expectations exist. But going to leave that sumption implicit. Fortunately, random variables without expectations don't arise too often in practice 2 The Coupon Collector Problem Every time I purchase a kid's meal at Taco Bell, I am graciously presented with a miniature Racin Rocket"car together with a launching device which enables me to project my new

2 Expected Value II • Otherwise, there are several numbers tied for largest. My number is as likely to be one of these as any of your numbers, so with probability greater than 1/(k + 1) you must pick again. In both cases, with probability at least 1/(k + 1), you need more than k picks to beat me. In other words: 1 Pr (# times you pick > k) ≥ (2) k + 1 This suggests that in order to minimize your rolls, you should chose a distribution such that ties are very rare. For example, you might choose the uniform distribution on {1, 2, . . . , 10100}. In this case, the probability that you need more than k picks to beat me is very close to 1/(k+1) for moderate values of k. For example, the probability that you need more than 99 picks is almost exactly 1%. This sounds very promising for you; intuitively, you might expect to win within a reasonable number of picks on average! Unfortunately for intuition, there is a simple proof that the expected number of picks that you need in order to beat me is infinite, regardless of the distribution! Let’s plug (2) into (1): � 1 ∞ Ex (# times you pick) = k + 1 k=0 = ∞ This phenomenon can cause all sorts of confusion! For example, suppose you have a communication network where each packet of data has a 1/k chance of being delayed by k or more steps. This sounds good; there is only a 1% chance of being delayed by 100 or more steps. But the expected delay for the packet is actually infinite! There is a larger point here as well: not every random variable has a well­defined expectation. This idea may be disturbing at first, but remember that an expected value is just a weighted average. And there are many sets of numbers that have no conventional average either, such as: {1, −2, 3, −4, 5, −6, . . .} Strictly speaking, we should qualify virtually all theorems involving expectation with phrases such as “...provided all expectations exist.” But we’re going to leave that as￾sumption implicit. Fortunately, random variables without expectations don’t arise too often in practice. 2 The Coupon Collector Problem Every time I purchase a kid’s meal at Taco Bell, I am graciously presented with a miniature “Racin’ Rocket” car together with a launching device which enables me to project my new

Expected value Il vehicle across any tabletop or smooth floor at high velocity. Truly, my delight knows no bounds There are n different types of Racin Rocket car(blue, green, red, gray, etc. ) The type of car awarded to me each day by the kind woman at the Taco Bell register appears to be elected uniformly and independently at random. What is the expected number of kids meals that I must purchase in order to acquire at least one of each type of Racin Rocket car The same mathematical question shows up in many for example, what is the expected number of people you must poll in order to find at least one person with each possible birthday? Here, instead of collecting RacinRocket cars, you re collecting birth days. The general question is commonly called the coupon collector problem after yet another interpretation 2.1 A Solution Using Linearity of Expectation Linearity of expectation is somewhat like induction and the pigeonhole principle; it's a simple idea that can be used in all sorts of ingenious ways. For example, we can use linearity of expectation in a clever way to solve the coupon collector problem. Suppose there are five different types of Racin'Rocket, and I receive this sequence blue greengreen red blue orange blue orange gray Let's partition the sequence into 5 segments blue green green red blue orange blue orange gray The rule is that a segment ends whenever I get a new kind of car. For example, the middle segment ends when I get a red car for the first time. In this way, we can break the problem of collecting every type of car into stages. Then we can analyze each stage individually nd assemble the results using linearity of expectation. ya Let's return to the general case where I'm collecting n Racin Rockets. Let X, be the length of the k-th segment. The total number of kid's meals I must purchase to get all n Racin Rockets is the sum of the lengths of all these segments T=X0+X1+ Now let's focus our attention of the Xk, the length of the k-th segment. At the begin ning of segment k, I have k different types of car, and the segment ends when I acquire a new type. When I own k types, each kid's meal contains a type that I already have with probability k/n. Therefore, each meal contains a new type of car with probability k/n=(n-k)/n. Thus, the expected number of meals until i get a new kind of car

Expected Value II 3 vehicle across any tabletop or smooth floor at high velocity. Truly, my delight knows no bounds. There are n different types of Racin’ Rocket car (blue, green, red, gray, etc.). The type of car awarded to me each day by the kind woman at the Taco Bell register appears to be selected uniformly and independently at random. What is the expected number of kids meals that I must purchase in order to acquire at least one of each type of Racin’ Rocket car? The same mathematical question shows up in many guises: for example, what is the expected number of people you must poll in order to find at least one person with each possible birthday? Here, instead of collecting Racin’ Rocket cars, you’re collecting birth￾days. The general question is commonly called the coupon collector problem after yet another interpretation. 2.1 A Solution Using Linearity of Expectation Linearity of expectation is somewhat like induction and the pigeonhole principle; it’s a simple idea that can be used in all sorts of ingenious ways. For example, we can use linearity of expecatation in a clever way to solve the coupon collector problem. Suppose there are five different types of Racin’ Rocket, and I receive this sequence: blue green green red blue orange blue orange gray Let’s partition the sequence into 5 segments: blue green green red blue orange blue orange gray ���� � �� � � �� � � �� � � �� � X0 X1 X2 X3 X4 The rule is that a segment ends whenever I get a new kind of car. For example, the middle segment ends when I get a red car for the first time. In this way, we can break the problem of collecting every type of car into stages. Then we can analyze each stage individually and assemble the results using linearity of expectation. Let’s return to the general case where I’m collecting n Racin’ Rockets. Let Xk be the length of the k­th segment. The total number of kid’s meals I must purchase to get all n Racin’ Rockets is the sum of the lengths of all these segments: T = X0 + X1 + . . . + Xn−1 Now let’s focus our attention of the Xk, the length of the k­th segment. At the begin￾ning of segment k, I have k different types of car, and the segment ends when I acquire a new type. When I own k types, each kid’s meal contains a type that I already have with probability k/n. Therefore, each meal contains a new type of car with probability 1 − k/n = (n − k)/n. Thus, the expected number of meals until I get a new kind of car

Expected Value I is n/(n-k)by the"mean time to failure"formula that we worked out last time. So we have Ex(xk)= Linearity of expectation together with this observation solves the coupon collector obler (T)=Ex(Xo+X1 =Ex(X0)+Ex(X1)+…+Ex(Xn-1) nnn n-0n-1 111 =n(-+ n n-1 nh order. As you may recall, this sum is denoted Hn and is approximately lnn ns in reverse The summation on the next-to-last line is the n-th harmonic sum with the terms in reverse Let's use this general solution to answer some concrete questions. For example, the expected number of die rolls required to see every number from 1 to 6 is 6H6=14.7 And the expected number of people you must poll to find at least one person with each possible birthday is 365H365=2364.6 3 Expected Value of a Product Enough with sums! What about the expected value of a product of random variables? If Ri and R2 are independent, then the expected value of their product is the product of their expected values Theorem 1. For independent random variables Ri and R2 Ex(R1·B2)=Ex(R1)·Ex(B2) Proof. Well transform the right side into the left side Ex(B)Ex(B)=(∑xP(B1=)∑vP(B=0) r∈ Range(R1) x∈ Range(R1) y Pr(ri=aPr(ri=y r∈ Range(R1)y∈ Range(R2) ∑∑xyP(R1=∩R1=y) rERange(R1)yERange(R2)

� � � � � � � � 4 Expected Value II is n/(n − k) by the “mean time to failure” formula that we worked out last time. So we have: n Ex (Xk) = n − k Linearity of expecatation, together with this observation, solves the coupon collector problem: Ex (T) = Ex (X0 + X1 + . . . + Xn−1) = Ex (X0) + Ex (X1) + . . . + Ex (Xn−1) n n n n n = + + . . . + + + n − 0 n − 1 3 2 1 1 1 1 1 1 = n + + . . . + + + n n − 1 3 2 1 = nHn The summation on the next­to­last line is the n­th harmonic sum with the terms in reverse order. As you may recall, this sum is denoted Hn and is approximately ln n. Let’s use this general solution to answer some concrete questions. For example, the expected number of die rolls required to see every number from 1 to 6 is: 6H6 = 14.7 . . . And the expected number of people you must poll to find at least one person with each possible birthday is: 365H365 = 2364.6 . . . 3 Expected Value of a Product Enough with sums! What about the expected value of a product of random variables? If R1 and R2 are independent, then the expected value of their product is the product of their expected values. Theorem 1. For independent random variables R1 and R2: Ex (R1 · R2) = Ex (R1) · Ex (R2) Proof. We’ll transform the right side into the left side: ⎛ ⎞ ⎛ ⎞ Ex (R1) · Ex (R2) = ⎝ x · Pr (R1 = x)⎠ ⎝· y · Pr (R2 = y)⎠ x∈Range(R1) x∈Range(R1) = xy Pr (R1 = x) Pr (R1 = y) x∈Range(R1) y∈Range(R2) = xy Pr (R1 = x ∩ R1 = y) x∈Range(R1) y∈Range(R2)

Expected value Il The second line comes from multiplying out the product of sums. Then we used the fact that R1 and R2 are independent. Now let's group terms for which the product y is the same ∑∑xP(B1=x∩R1=) 2(2 Pru,-n R, -D) Pr(R1·R2=x) =Ex(R1·R2) 3.1 The Product of Two Independent dice Suppose we throw two independent, fair dice and multiply the numbers that come up What is the expected value of this product? Let random variables R, and Ro be the numbers shown on the two dice. We can com pute the expected value of the product as follows Ex(Ri. R2)=Ex(r1). Ex(r2) 12 On the first line, were using Theorem 1. Then we use the result from last lecture that the cted value of one die is 3 3.2 The Product of Two Dependent dice Suppose that the two dice are not independent; in fact, suppose that the second die is always the same as the first. Does this change the expected value of the product? Is the dependence condition in Theorem 1 really necessary? As before, let random variables Ri and R2 be the numbers shown on the two dice. We

� � � � � � � Expected Value II 5 The second line comes from multiplying out the product of sums. Then we used the fact that R1 and R2 are independent. Now let’s group terms for which the product xy is the same: = xy Pr (R1 = x ∩ R1 = y) z∈Range(R1·R2) x,y: xy=z = z Pr (R1 = x ∩ R1 = y) z∈Range(R1·R2) x,y: xy=z = z · Pr (R1 · R2 = z) z∈Range(R1·R2) = Ex (R1 · R2) 3.1 The Product of Two Independent Dice Suppose we throw two independent, fair dice and multiply the numbers that come up. What is the expected value of this product? Let random variables R1 and R2 be the numbers shown on the two dice. We can com￾pute the expected value of the product as follows: Ex (R1 · R2) = Ex (R1) · Ex (R2) 1 1 = 3 3 2 · 2 1 = 12 4 On the first line, we’re using Theorem 1. Then we use the result from last lecture that the expected value of one die is 3 1 . 2 3.2 The Product of Two Dependent Dice Suppose that the two dice are not independent; in fact, suppose that the second die is always the same as the first. Does this change the expected value of the product? Is the independence condition in Theorem 1 really necessary? As before, let random variables R1 and R2 be the numbers shown on the two dice. We

ected value li can compute the expected value of the product directly as follows ∑2P(Rn1=i) 122232425262 6 6+6+6+6 The first step uses the fact that the outcome of the second die is always the same as the first. Then we expand Ex(Ri)using one of our formulations of expectation. Now that the dice are no longer independent, the expected value of the product has changed to 156. So the expectation of a product of dependent random variables need not equal the product of their expectations 3.3 Corollaries Theorem l extends to a collection of mutually independent variables Corollary 2. If random variables R1, R2,..., Rn are mutually independent, then Ex(B1·R2…Rn)=Ex(R1)·Ex(R2)…Ex(Rn) on The proof uses induction, Theorem 1, and the definition of mutual independence. We'll nit the detail o We now know the expected value of a sum or product of random variables. Unfortu- tely, the expected value of a reciprocal is not so easy to characterize. Here is a fla attempt False Corollary 3. If R is a random variable, then Ex As a counterexample, suppose the random variable R is l with probability 2 and is 2 ith probability Then we have Ex(B)1·+2 1-13-4 2+22

� � � � � 6 Expected Value II can compute the expected value of the product directly as follows: Ex (R1 R2) = Ex R2 1 · 6 = i 2 · Pr(R1 = i) i=1 12 22 32 42 52 62 = + + + + + 6 6 6 6 6 6 1 = 15 6 The first step uses the fact that the outcome of the second die is always the same as the first. Then we expand Ex (R2 1) using one of our formulations of expectation. Now that the dice are no longer independent, the expected value of the product has changed to 15 1 . So 6 the expectation of a product of dependent random variables need not equal the product of their expectations. 3.3 Corollaries Theorem 1 extends to a collection of mutually independent variables. Corollary 2. If random variables R1, R2, . . . , Rn are mutually independent, then Ex (R1 · · · · R2 Rn) = Ex (R1) · Ex (R2)· · ·Ex (Rn) The proof uses induction, Theorem 1, and the definition of mutual independence. We’ll omit the details. We now know the expected value of a sum or product of random variables. Unfortu￾nately, the expected value of a reciprocal is not so easy to characterize. Here is a flawed attempt. False Corollary 3. If R is a random variable, then 1 1 Ex = R Ex (R) As a counterexample, suppose the random variable R is 1 with probability 1 and is 2 2 with probability 1 . Then we have: 2 1 1 = 1 1 Ex (R) 2 2 + 2 1 · · 2 = � � 3 1 1 1 1 1 Ex = + R 1 · 2 2 · 2 3 = 4

Expected value Il The two quantities are not equal, so the corollary must be false. But here is another false corollary, which we can actually prove"! False Corollary 4. IfEx(r/T)>l, then Ex (r)> Ex t Proof. We begin with the if-Part, multiply both sides by Ex (T), and then apply Theo- rem Ex(r/T)>1 Ex(R/T)·Ex(T)>Ex(T) Ex(r)>Ex(T) This "proof"is bogus! The first step is valid only if Ex(T)>0. More importantly, we cant apply Theorem 1 in the second step because R/T and T are not necessarily independent. Unfortunately, the fact that Corollary 4 is false does not mean it is never 3.3.1 A RISC Paradox The following data is taken from a paper by some famous professors. They wanted to show that programs on a RiSC processor are generally shorter than programs on a CISC processor. For this purpose, they made a table of program lengths for some benchmark problems, which looked like this Benchmark RISC CISC CISC/ RISC E-string search 150 120 0.8 F-bit test 120180 1.5 Ackerman 150300 Rec 2-sort 28001400 0.5 1.2 Each row contains the data for one benchmark. The numbers in the first two columns are program lengths for each type of processor. The third column contains the ratio of the CISC program length to the RISC program length. Averaging this ratio over all bench- marks gives the value 1. 2 in the lower right. The authors conclude that"CISC programs are 20% longer on averag But there's a pretty serious problem here. Suppose we redo the final column, taking the inverse ratio, risc / CISC instead of CiSc/ risc Benchmark RISC CISC RISC/CISC E-str ng F-bit test 120180 0.67 Ackerman 150300 0.5 Rec 2-sort 28001400 A

Expected Value II 7 The two quantities are not equal, so the corollary must be false. But here is another false corollary, which we can actually “prove”! False Corollary 4. If Ex (R/T) > 1, then Ex (R) > Ex (T). “Proof”. We begin with the if­part, multiply both sides by Ex (T), and then apply Theo￾rem 1: Ex (R/T) > 1 Ex (R/T) · Ex (T) > Ex (T) Ex (R) > Ex (T) This “proof” is bogus! The first step is valid only if Ex (T) > 0. More importantly, we can’t apply Theorem 1 in the second step because R/T and T are not necessarily independent. Unfortunately, the fact that Corollary 4 is false does not mean it is never used! 3.3.1 A RISC Paradox The following data is taken from a paper by some famous professors. They wanted to show that programs on a RISC processor are generally shorter than programs on a CISC processor. For this purpose, they made a table of program lengths for some benchmark problems, which looked like this: Benchmark RISC CISC CISC / RISC E­string search 150 120 0.8 F­bit test 120 180 1.5 Ackerman 150 300 2.0 Rec 2­sort 2800 1400 0.5 Average 1.2 Each row contains the data for one benchmark. The numbers in the first two columns are program lengths for each type of processor. The third column contains the ratio of the CISC program length to the RISC program length. Averaging this ratio over all bench￾marks gives the value 1.2 in the lower right. The authors conclude that “CISC programs are 20% longer on average”. But there’s a pretty serious problem here. Suppose we redo the final column, taking the inverse ratio, RISC / CISC instead of CISC / RISC. Benchmark RISC CISC RISC / CISC E­string search 150 120 1.25 F­bit test 120 180 0.67 Ackerman 150 300 0.5 Rec 2­sort 2800 1400 2.0 Average 1.1

Expected Value I By exactly the same reasoning used by the authors, we could conclude that risc pro- grams are 10% longer on average than CISC programs! What's going on? 3.3.2 A Probabilistic Interpretation To shed some light on this paradox, we can model the risC vs. CISC debate with the machinery of probability theory Let the sample space be the set of benchmark programs. Let the random variable R be the length of the RiSC program, and let the random variable c be the length of the CiSC program. We would like to compare the average length of a RiSC program, Ex(R), to the average length of a CISC program, Ex(C) To compare average program lengths, we must assign a probability to each sample point; in effect, this assigns a"weight"to each benchmark. One might like to weigh benchmarks based on how frequently similar programs arise in practice. But let's follow the original authors'lead. They assign each ratio equal weight in their average, so theyre implicitly assuming that similar programs arise with equal probability. Let's do that same and make the sample space uniform. We can now compute Ex(r)and Ex (C)as follows 1501201502800 Ex 4+4+4 =805 Ex(C)=120180300140 4 =500 he average length of a RISC program is actually Ex(R)/Ex(C)=1.61 times greater Pre, the average length of a CISC program. RISC is even worse than either of the two previous answers would suggest! In terms of our probability model, the authors computed C/R for each sample point and then averaged to obtain Ex(C/R)=1. 2. This much is correct. However, they inter- pret this to mean that CiSC programs are longer than RiSC programs on average. Thus, the key conclusion of this milestone paper rests on Corollary 4, which we know to be false! 3.3.3 A Simpler Example The root of the problem is more clear in the following, simpler example. Suppose the data were as follows Benchmark Processor A Processor BB/AA/B Problem 1 2 Problem 2 2 21/2 Average 1.251.25

8 Expected Value II By exactly the same reasoning used by the authors, we could conclude that RISC pro￾grams are 10% longer on average than CISC programs! What’s going on? 3.3.2 A Probabilistic Interpretation To shed some light on this paradox, we can model the RISC vs. CISC debate with the machinery of probability theory. Let the sample space be the set of benchmark programs. Let the random variable R be the length of the RISC program, and let the random variable C be the length of the CISC program. We would like to compare the average length of a RISC program, Ex (R), to the average length of a CISC program, Ex (C). To compare average program lengths, we must assign a probability to each sample point; in effect, this assigns a “weight” to each benchmark. One might like to weigh benchmarks based on how frequently similar programs arise in practice. But let’s follow the original authors’ lead. They assign each ratio equal weight in their average, so they’re implicitly assuming that similar programs arise with equal probability. Let’s do that same and make the sample space uniform. We can now compute Ex (R) and Ex (C) as follows: 150 120 150 2800 Ex (R) = + + + 4 4 4 4 = 805 120 180 300 1400 Ex (C) = + + + 4 4 4 4 = 500 So the average length of a RISC program is actually Ex (R) /Ex (C) = 1.61 times greater than the average length of a CISC program. RISC is even worse than either of the two previous answers would suggest! In terms of our probability model, the authors computed C/R for each sample point and then averaged to obtain Ex (C/R) = 1.2. This much is correct. However, they inter￾pret this to mean that CISC programs are longer than RISC programs on average. Thus, the key conclusion of this milestone paper rests on Corollary 4, which we know to be false! 3.3.3 A Simpler Example The root of the problem is more clear in the following, simpler example. Suppose the data were as follows. Benchmark Processor A Processor B B/A A/B Problem 1 2 1 1/2 2 Problem 2 1 2 2 1/2 Average 1.25 1.25

Expected value Il Now the statistics for processors A and b are exactly symmetric. Yet, from the third col- umn we would conclude that Processor B programs are 25% longer on average, and from the fourth column we would conclude that Processor a programs are 25% longer on av- erage. Both conclusions are obviously wrong. The moral is that averages of ratios can be very misleading. More generally, if you're computing the expectation of a quotient, think twice; you're going to get a value ripe for misuse and misinterpretation. 4 The Total Expectation Theorem Earlier we talked about conditional probability. For example, you might want to know the probability that someone was dealt at least two aces, given that they were dealt the ace of spades. Similarly, one can talk about conditional expectation. For example, you could determine the expected number that comes up on a fair die given that the roll is even There are several ways to compute a conditional expectation, just as there are several ways to compute an ordinary expectation. In fact, the conditional expectation formulas are the same as the ordinary expectation formulas, except that all the probabilities become conditional probabilities. If R is a random variable and E is an event, then the expected value of r given that event E occurs is denoted Ex(r e)and defined by Ex(r E)=> R(w)Pr(w| E) u∈S ∑x:P(R=x|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(r e), the expected value of a die roll, given that the result is even Ex(|E)=∑R()P1(|E) u∈{1,…6} 4 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 Theorem Theorem 5 (Total Expectation). Let E1,..., En be events that partition the sample space and have nonzero probabilities. If R is a random variable, then Ex(B)=Ex(B|E1)·Pr(E1)+…+Ex(f|En)·Pr(E)

� � � Expected Value II 9 Now the statistics for processors A and B are exactly symmetric. Yet, from the third col￾umn we would conclude that Processor B programs are 25% longer on average, and from the fourth column we would conclude that Processor A programs are 25% longer on av￾erage. Both conclusions are obviously wrong. The moral is that averages of ratios can be very misleading. More generally, if you’re computing the expectation of a quotient, think twice; you’re going to get a value ripe for misuse and misinterpretation. 4 The Total Expectation Theorem Earlier we talked about conditional probability. For example, you might want to know the probability that someone was dealt at least two aces, given that they were dealt the ace of spades. Similarly, one can talk about conditional expectation. For example, you could determine the expected number that comes up on a fair die given that the roll is even. There are several ways to compute a conditional expectation, just as there are several ways to compute an ordinary expectation. In fact, the conditional expectation formulas are the same as the ordinary expectation formulas, except that all the probabilities become conditional probabilities. If R is a random variable and E is an event, then the expected value of R given that event E occurs is denoted Ex (R | E) and defined by: Ex (R | E) = R(w) Pr (w | E) w∈S = x · Pr (R = x | E) x∈ range(R) 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 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 Theorem: Theorem 5 (Total Expectation). Let E1, . . . , En be events that partition the sample space and have nonzero probabilities. If R is a random variable, then: Ex (R) = Ex (R | E1) · Pr (E1) + · · · + Ex (R E| n) · Pr (En)

Expected Value I 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 say Ex(R)=Ex(R E)Pr(E)+Ex(r e).Pr =7/2 1/2 The only quantity here that we don t already know is Ex(RI E), 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 E Proof. Note that for any outcome, s, in the sample space, Pr({s}∩E)= [Pr(s)if IE(s)=1, Pr({s}∩E)=IE(s)·Pr(s) (4) Ex(R E)=>R(s). Pr(s)IE ofEx(·|E) ∑().P(nE Pr(e) ( Def of Pr(·|E) RLS IE(s). Pr(s) Pr(e) (by(4) R(s)·IE(s)·Pr(s) (E) Ex(R·IE ( Def of Ex(R·IE) Now we prove the Total Expectation Theorem

� � � � � � � � � � 10 Expected Value II 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 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) = · (3) 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). (4) Now, Ex (R | E) = R(s) · Pr ({s} | E) (Def of Ex (· | E)) s∈S R(s) · Pr ({ = s} ∩ E) (Def of Pr (· | E)) Pr (E) s∈S � IE(s) · Pr (s) = R(s) · (by (4)) Pr (E) s∈S s∈S(R(s) · IE(s)) · Pr (s) = Pr (E) Ex (R IE) = · (Def of Ex (R IE)) Pr (E) · Now we prove the Total Expectation Theorem: