Mathematics for Computer Science

Chapter 19 Deviation from the Mean804

In particular, for a class ofnD 95 students withdD 365 possible birthdays, we
have ExŒMç12:23and VarŒMç12:23.11=365/ < 12:2. So by Chebyshev’s
Theorem

PrŒjMExŒMçjxç <

12:2

x^2

:

LettingxD 7 , we conclude that there is a better than 75% chance that in a class of
95 students, the number of pairs of students with the same birthday will be within
7 of 12.23, that is, between 6 and 19.

19.4.3 Pairwise Independent Sampling

The reasoning we used above to analyze voter polling and matching birthdays is
very similar. We summarize it in slightly more general form with a basic result
called the Pairwise Independent Sampling Theorem. In particular, we do not need
to restrict ourselves to sums of zero-one valued variables, or to variables with the
same distribution. For simplicity, we state the Theorem for pairwise independent
variables with possibly different distributions but with the same mean and variance.

Theorem 19.4.1(Pairwise Independent Sampling). LetG 1 ;:::;Gnbe pairwise
independent variables with the same mean,, and deviation,. Define

SnWWD

Xn

iD 1

Gi: (19.22)

Then

Pr

ˇˇ

ˇ

ˇ

Sn

n



ˇ

ˇˇ

ˇx





1

n



x

 2

:

Proof. We observe first that the expectation ofSn=nis:

Ex



Sn

n



DEx

Pn

iD 1 Gi

n



(def ofSn)

D

Pn

iD 1 ExŒGiç

n

(linearity of expectation)

D

Pn

iD 1 

n

D

n

n

D:

The second important property ofSn=nis that its variance is the variance ofGi