Mathematics for Computer Science

Chapter 19 Deviation from the Mean814

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 real intervalŒ0;1ç. 

19.6.7 Comparing the Bounds

Suppose that we have a collection of mutually independent eventsA 1 ,A 2 ,... ,An,
and we want to know how many of the events are likely to occur.
LetTibe the indicator random variable forAiand define

piDPrŒTiD1çDPr



Ai



for 1 in. Define
T DT 1 CT 2 C


CTn

to be the number of events that occur.
We know from Linearity of Expectation that

ExŒTçDExŒT 1 çCExŒT 2 çC


CExŒTnç

D

Xn

iD 1

pi:

This is true even if the events arenotindependent.
By Theorem 19.3.8, we also know that

VarŒTçDVarŒT 1 çCVarŒT 2 çC


CVarŒTnç

D

Xn

iD 1

pi.1pi/;

and thus that

TD

vu

u

t

Xn

iD 1

pi.1pi/:

This is true even if the events are only pairwise independent.
Markov’s Theorem tells us that for anyc > 1,

PrŒTcExŒTçç

1

c

: