Mathematics for Computer Science

19.4. Estimation by Random Sampling 805

divided byn:

Var



Sn

n



D



1

n

 2

VarŒSnç (Square Multiple Rule for Variance (19.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

: (19.23)

This is enough to apply Chebyshev’s Theorem and conclude:

Pr

ˇˇ

ˇ

ˇ

Sn

n



ˇ

ˇˇ

ˇx





VarŒSn=nç

x^2

: (Chebyshev’s bound)

D

^2 =n

x^2

(by (19.23))

D

1

n



x

 2

:



The Pairwise Independent Sampling Theorem provides a quantitative general
statement about how the average of independent samples of a random variable ap-
proaches the mean. In particular, it proves what is known as the Law of Large
Numbers^4 : by choosing a large enough sample size, we can get arbitrarily accurate
estimates of the mean with confidence arbitrarily close to 100%.

Corollary 19.4.2.[Weak Law of Large Numbers] LetG 1 ;:::;Gnbe pairwise in-
dependent variables with the same mean,, and the same finite deviation, and
let

SnWWD

Pn

iD 1 Gi

n

:

Then for every > 0,
lim
n!1
PrŒjSnjçD1:

(^4) This is theWeakLaw of Large Numbers. As you might suppose, there is also a Strong Law, but
it’s outside the scope of 6.042.