Mathematics for Computer Science

17.5. Linearity of Expectation 599

LettingGbe the number of men that get their own hat, we want to find the
expectation ofG. But all we know aboutGis that the probability that a man gets
his own hat back is1=n. There are many different probability distributions of hat
permutations with this property, so we don’t know enough about the distribution
ofGto calculate its expectation directly. But linearity of expectation makes the
problem really easy.
The trick^3 is to expressGas a sum of indicator variables. In particular, letGibe
an indicator for the event that theith man gets his own hat. That is,GiD 1 if the
ith man gets his own hat, andGiD 0 otherwise. The number of men that get their
own hat is then the sum of these indicator random variables:

GDG 1 CG 2 C


CGn: (17.9)

These indicator variables arenotmutually independent. For example, ifn 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!
SinceGiis an indicator random variable, we know from Lemma 17.4.2 that

ExŒGiçDPrŒGiD1çD1=n: (17.10)

By Linearity of Expectation and equation (17.9), this means that

ExŒGçDExŒG 1 CG 2 C


CGnç

DExŒG 1 çCExŒG 2 çC


CExŒGnç

D

n

‚ ...„ ƒ

1

n

C

1

n

C


C

1

n

D1:

So even though we don’t know much about how hats are scrambled, we’ve figured
out that on average, just one man gets his own hat back!
More generally, Linearity of Expectation provides a very good method for com-
puting the expected number of events that will happen.

Theorem 17.5.4. Given any collection of eventsA 1 ;A 2 ;:::;An, the expected
number of events that will occur is

Xn

iD 1

PrŒAiç:

(^3) We are going to use this trick a lot so it is important to understand it.