Expected value I So now we need only compute Pr(Ri= 1), which is the probability that the ith man gets his own hat. Since every man is as likely to get one hat as another, this is just 1/n Putting all this together, we have Ex(r)=Ex(r1)+Ex(r2)+.+ Ex(r Pr(R1=1)+Pr(R2=1)+…+Pr(Rn=1) n o we should expect 1 man to get his own hat back on average Notice that we did not assume that all permutations of hats are equally likely or even that all permutations are possible. We only needed to know that each man received his own hat with probability 1/n. This makes our solution very general, as the next example shows 3.3 The Chinese Appetizer Problem There are n people at a circular table in a Chinese restaurant. On the there are n different appetizers arranged on a big Lazy Susan. person starts appetizer directly in front of him or her. Then someone spins the Lazy Susan so that everyone is faced with a random appetizer. What is the expected number of people that end up with the appetizer that they had originally? This is just a special case of the hat-check problem, with appetizers in place of hats In the hat-check problem, we assumed only that each man received his own hat with probability 1/n. Beyond that, we made no assumptions about how the hats could be permuted. This problem is a special case because we happen to know that appetizers are cyclically shifted relative to their initial position. This means that either everyone gets their original appetizer back, or no one does. But our previous analysis still holds: the expected number of people that get their own appetizer back is 1Expected Value I 9 So now we need only compute Pr(Ri = 1), which is the probability that the ith man gets his own hat. Since every man is as likely to get one hat as another, this is just 1/n. Putting all this together, we have: Ex (R) = Ex (R1) + Ex (R2) + · · · + Ex (Rn) = Pr (R1 = 1) + Pr (R2 = 1) + · · · + Pr (Rn = 1) 1 = n · = 1. n So we should expect 1 man to get his own hat back on average! Notice that we did not assume that all permutations of hats are equally likely or even that all permutations are possible. We only needed to know that each man received his own hat with probability 1/n. This makes our solution very general, as the next example shows. 3.3 The Chinese Appetizer Problem There are n people at a circular table in a Chinese restaurant. On the table, there are n different appetizers arranged on a big Lazy Susan. Each person starts munching on the appetizer directly in front of him or her. Then someone spins the Lazy Susan so that everyone is faced with a random appetizer. What is the expected number of people that end up with the appetizer that they had originally? This is just a special case of the hat­check problem, with appetizers in place of hats. In the hat­check problem, we assumed only that each man received his own hat with probability 1/n. Beyond that, we made no assumptions about how the hats could be permuted. This problem is a special case because we happen to know that appetizers are cyclically shifted relative to their initial position. This means that either everyone gets their original appetizer back, or no one does. But our previous analysis still holds: the expected number of people that get their own appetizer back is 1