Mathematics for Computer Science

17.4. Great Expectations 591

of the firsti 1 hours, times the probability,p, that it does crash in theith hour.
So

ExŒCçD

X

i 2 N

i
PrŒCDiç (by (17.2))

D

X

i 2 N

i.1p/i^1 p

D

p

1 p

X

i 2 N

i.1p/i: (17.7)

But we’ve already seen a sum like this last one (you did remember this, right?),
namely, equation (14.13): X

i 2 N

ixiD

x

.1x/^2

:

Combining (14.13) with (17.7) gives

ExŒCçD

p

1 p

1 p

.1.1p//^2

D

1

p

as expected.
For the record, we’ll state a formal version of this result. A random variable
likeCthat counts steps to first failure is said to have ageometric distributionwith
paramterp.
Definition 17.4.7.A random variable,C, has ageometric distributionwith paramter
piff codomain.C/DZCand

PrŒCDiçD.1p/i^1 p:

Lemma 17.4.8.If a random variableChad a geometric distribution with paramter
p, then

ExŒCçD

1

p

: (17.8)

17.4.7 Expected Returns in Gambling Games

Some of the most interesting examples of expectation can be explained in terms of
gambling games. For straightforward games where you winwdollars with proba-
bilitypand you losexdollars with probability 1 p, it is easy to compute your
expected returnorwinnings. It is simply

pw.1p/xdollars: