Mathematics for Computer Science

19.6. Sums of Random Variables 813

Algebra aside, there is a brilliant idea in this proof: in this context, exponenti-
ating somehow supercharges the Markov bound. This is not true in general! One
unfortunate side-effect of this supercharging is that we have to bound some nasty
expectations involving exponentials in order to complete the proof. This is done in
the two lemmas below, where variables take on values as in Theorem 19.6.1.

Lemma 19.6.2.
Ex

h

cT

i

e.c1/ExŒTç:

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 18.5.7)

e.c1/ExŒT^1 ç


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

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


CExŒTnç/

De.c1/ExŒT^1 C


CTnç (linearity of ExŒ
ç)

De.c1/ExŒTç:

The third equality depends on the fact that functions of independent variables are
also independent (see Lemma 18.2.2). 

Lemma 19.6.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):