Mathematics for Computer Science

17.4. Great Expectations 589

Proof.

ExŒRçD

X

r 2 range.R/

r
PrŒRDrç (by 17.2)

D

X

r

r

X

i

Pr



RDrjAi



PrŒAiç (Law of Total Probability)

D

X

r

X

i

r
Pr



RDrjAi



PrŒAiç (distribute constantr)

D

X

i

X

r

r
Pr



RDrjAi



PrŒAiç (exchange order of summation)

D

X

i

PrŒAiç

X

r

r
Pr



RDrjAi



(factor constant PrŒAiç)

D

X

i

PrŒAiçExŒRjAiç: (Def 17.4.5 of cond. expectation)



17.4.6 Mean Time to Failure

A computer program crashes at the end of each hour of use with probabilityp, if it
has not crashed already. What is the expected time until the program crashes? This
will be easy to figure out using the Law of Total Expectation (Theorem 17.4.6).
Specifically, we want to find ExŒCçwhereCis the number of hours until the first
crash. We’ll do this by conditioniing on whether or not the crash occurs in the first
hour.
So letAto be the event that the system fails on the first step andAto be the
complementary event that the system does not fail on the first step. Then the mean
time to failure ExŒCçis

ExŒCçDExŒCjAçPrŒAçCExŒCjAçPrŒAç: (17.4)

SinceAis the condition that the system crashes on the first step, we know that

ExŒCjAçD1: (17.5)

SinceAis the condition that the system doesnotcrash on the first step, conditioning
onAis equivalent to taking a first step without failure and then starting over without
conditioning. Hence,
ExŒCjAçD 1 CExŒCç: (17.6)