Mathematics for Computer Science

Chapter 18 Deviation from the Mean642

18.7.6 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 18.4.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

:

Chebyshev’s Theorem gives us the stronger result that

PrŒjTExŒTçjcTç

1

c^2

:

The Chernoff Bound gives us an even stronger result, namely, that for anyc > 0,

PrŒTExŒTçcExŒTççe.cln.c/cC1/ExŒTç: