Mathematics for Computer Science

Chapter 18 Deviation from the Mean632

18.5.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 we
call 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 18.5.1(Pairwise Independent Sampling). LetG 1 ;:::;Gnbe pairwise
independent variables with the same mean,, and deviation,. Define

SnWWD

Xn

iD 1

Gi: (18.21)

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
divided byn:

Var



Sn

n



D



1

n

 2

VarŒSnç (by (18.9))

D

1

n^2

Var

"n

X

iD 1

Gi

(def ofSn)

D

1

n^2

Xn

iD 1

VarŒGiç (pairwise independent additivity)

D

1

n^2

n^2 D

^2

n

: (18.22)