Expected value I 3.2 The hat-Check Problem There is a dinner party where n men check their hats. The hats are mixed up during dinner, so that afterward each man receives a random hat. In particular, each man gets his own hat with probability 1/n. What is the expected number of men who get their own hat Without linearity of expectation, this would be a very difficult question to answer. We might try the following. Let the random variable r be the number of men that get their own hat. We want to compute Ex(r). By the definition of expectation, we have k·Pr(R=k) Now were in trouble, because evaluating Pr(R=k) is a mess and we then need to substitute this mess into a summation. Furthermore, to have any hope, we would need to fix the probability of each permutation of the hats. For example, we might assume that all permutations of hats are equally likely. Now let's try to use linearity of expectation. As before, let the random variable r be the number of men that get their own hat. The trick is to express R as a sum of indicator variables. In particular, let R i be an indicator for the event that the ith man gets his own hat. That is, Ri= 1 is the event that he gets his own hat, and ri =0 is the event that he gets the wrong hat. The number of men that get their own hat is the sum of thes indicators R=R1+R2+…+Rn These indicator variables are not mutually independent. For example, if n-1 men all get their own hats, then the last man is certain to receive his own hat. But, since we plan to use linearity of expectation, we dont have worry about independence Let's take the expected value of both sides of the equation above and apply linearity Ex(R)=Ex(R1+ R2+.+Rn) Ex(R1)+Ex (r2)+.+Ex(R All that remains is to compute the expected value of the indicator variables Ri. Well use an elementary fact that is worth remembering in its own right Fact 1. The expected value of an indicator random variable is the probability that the indicator is 1. In symbols Ex (I=Pr(I=1) Proof. Ex()=1.Pr(I=1)+0·Pr(=0)� 8 Expected Value I 3.2 The Hat­Check Problem There is a dinner party where n men check their hats. The hats are mixed up during dinner, so that afterward each man receives a random hat. In particular, each man gets his own hat with probability 1/n. What is the expected number of men who get their own hat? Without linearity of expectation, this would be a very difficult question to answer. We might try the following. Let the random variable R be the number of men that get their own hat. We want to compute Ex (R). By the definition of expectation, we have: ∞ Ex (R) = k · Pr(R = k) k=0 Now we’re in trouble, because evaluating Pr(R = k) is a mess and we then need to substitute this mess into a summation. Furthermore, to have any hope, we would need to fix the probability of each permutation of the hats. For example, we might assume that all permutations of hats are equally likely. Now let’s try to use linearity of expectation. As before, let the random variable R be the number of men that get their own hat. The trick is to express R as a sum of indicator variables. In particular, let Ri be an indicator for the event that the ith man gets his own hat. That is, Ri = 1 is the event that he gets his own hat, and Ri = 0 is the event that he gets the wrong hat. The number of men that get their own hat is the sum of these indicators: R = R1 + R2 + + Rn · · · These indicator variables are not mutually independent. For example, if n − 1 men all get their own hats, then the last man is certain to receive his own hat. But, since we plan to use linearity of expectation, we don’t have worry about independence! Let’s take the expected value of both sides of the equation above and apply linearity of expectation: Ex (R) = Ex (R1 + R2 + · · · + Rn) = Ex (R1) + Ex (R2) + · · · + Ex (Rn) All that remains is to compute the expected value of the indicator variables Ri. We’ll use an elementary fact that is worth remembering in its own right: Fact 1. The expected value of an indicator random variable is the probability that the indicator is 1. In symbols: Ex (I) = Pr (I = 1) Proof. Ex (I) = 1 · Pr (I = 1) + 0 · Pr (I = 0) = Pr (I = 1)