Chapter 19 Deviation from the Mean814
The second step relies on the inequality
cv 1 C.c 1/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.c 1/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 CCTn
to be the number of events that occur.
We know from Linearity of Expectation that
ExŒTçDExŒT 1 çCExŒT 2 çCCExŒ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 çCCVarŒTnç
D
Xn
iD 1
pi.1 pi/;
and thus that
TD
vu
u
t
Xn
iD 1
pi.1 pi/:
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