Mathematics for Computer Science

17.5. Linearity of Expectation 603

of meals until we get a new kind of car isn=.nk/by the Mean Time to Failure
rule. This means that
ExŒXkçD

n

nk

:

Linearity of expectation, together with this observation, solves the coupon col-

lector problem:

ExŒTçDExŒX 0 CX 1 C


CXn 1 ç

DExŒX 0 çCExŒX 1 çC


CExŒXn 1 ç

D

n

n 0

C

n

n 1

C


C

n

3

C

n

2

C

n

1

Dn



1

n

C

1

n 1

C


C

1

3

C

1

2

C

1

1



Dn



1

1

C

1

2

C

1

3

C


C

1

n 1

C

1

n



DnHn (17.15)

nlnn:

Wow! It’s those Harmonic Numbers again!
We can use equation (17.15) to answer some concrete questions. For example,
the expected number of die rolls required to see every number from 1 to 6 is:

6H 6 D14:7::::

And the expected number of people you must poll to find at least one person with
each possible birthday is:

365H 365 D2364:6::::

17.5.5 Infinite Sums

Linearity of expectation also works for an infinite number of random variables
provided that the variables satisfy some stringent absolute convergence criteria.

Theorem 17.5.5(Linearity of Expectation).LetR 0 ,R 1 ,... , be random variables
such that 1
X

iD 0

ExŒjRijç