Mathematics for Computer Science

Chapter 18 Deviation from the Mean626

.CC1/^2. So

ExŒC^2 çDp
 12 C.1p/ExŒ.CC1/^2 ç

DpC.1p/



ExŒC^2 çC

2

p

C 1



DpC.1p/ExŒC^2 çC.1p/



2

p

C 1



; so

pExŒC^2 çDpC.1p/



2

p

C 1



D

p^2 C.1p/.2Cp/

p

and

ExŒC^2 çD

2 p

p^2

Combining this with (18.7) proves

Lemma 18.4.3.If failures occur with probabilitypindendently at each step, and
Cis the number of steps until the first failure^1 , then

VarŒCçD

1 p

p^2

: (18.8)

18.4.3 Dealing with Constants

It helps to know how to calculate the variance ofaRCb:

Theorem 18.4.4.LetRbe a random variable, andaa constant. Then

VarŒaRçDa^2 VarŒRç: (18.9)

Proof. Beginning with the definition of variance and repeatedly applying linearity
of expectation, we have:

VarŒaRçWWDExŒ.aRExŒaRç/^2 ç

DExŒ.aR/^2 2aRExŒaRçCEx^2 ŒaRçç

DExŒ.aR/^2 çExŒ2aRExŒaRççCEx^2 ŒaRç

Da^2 ExŒR^2 ç 2 ExŒaRçExŒaRçCEx^2 ŒaRç

Da^2 ExŒR^2 ça^2 Ex^2 ŒRç

Da^2

ExŒR^2 çEx^2 ŒRç

Da^2 VarŒRç (by Lemma 18.4.1)

(^1) That is,Chas the geometric distribution with parameterpaccording to Definition 17.4.7.