Mathematics for Computer Science

Chapter 19 Deviation from the Mean798

.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 (19.7) proves

Lemma 19.3.3.If failures occur with probabilitypindependently at each step, and
Cis the number of steps until the first failure^2 , then

VarŒCçD

1 p

p^2

: (19.8)

19.3.3 Dealing with Constants

It helps to know how to calculate the variance ofaRCb:

Theorem 19.3.4.[Square Multiple Rulefor Variance] LetRbe a random variable
andaa constant. Then
VarŒaRçDa^2 VarŒRç: (19.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ç (Lemma 19.3.1)

(^2) That is,Chas the geometric distribution with parameterpaccording to Definition 18.4.6.