Mathematics for Computer Science

18.7. Sums of Random Variables 641

Proof.

Ex

h

cT

i

DEx

h

cT^1 C


CTn

i

(def ofT)

DEx

h

cT^1 


cTn

i

DEx

h

cT^1

i




ExŒcTnç (independent product Cor 17.5.7)

e.c1/ExŒT^1 ç


e.c1/ExŒTnç (by Lemma 18.7.3 below)

De.c1/.ExŒT^1 çC


CExŒTnç/

De.c1/ExŒT^1 C


CTnç (linearity of ExŒ
ç)

De.c1/ExŒTç:



Lemma 18.7.3.
ExŒcTiçe.c1/ExŒTiç

Proof. All summations below range over valuesvtaken by the random variableTi,
which are all required to be in the intervalŒ0;1ç.

ExŒcTiçD

X

cvPrŒTiDvç (def of ExŒ
ç)



X

.1C.c1/v/PrŒTiDvç (convexity —see below)

D

X

PrŒTiDvçC.c1/vPrŒTiDvç

D

X

PrŒTiDvçC.c1/

X

vPrŒTiDvç

D 1 C.c1/ExŒTiç

e.c1/ExŒTiç (since 1 Czez):

The second step relies on the inequality

cv 1 C.c1/v;

which holds for allvinŒ0;1çandc 1. This follows from the general principle
that a convex function, namelycv, is less than the linear function, 1 C.c1/v,
between their points of intersection, namelyvD 0 and 1. This inequality is why
the variablesTiare restricted to the intervalŒ0;1ç.