Mathematics for Computer Science

Chapter 18 Deviation from the Mean654

is sufficient to be so confident.
Suppose you were were the defendent. How would you explain to the judge
why the number of randomly selected cars that have to be checked for speeding
does not depend on the number of recorded trips? Remember that judges are not
trained to understand formulas, so you have to provide an intuitive, nonquantitative
explanation.

Problem 18.13.
The proof of the Pairwise Independent Sampling Theorem 18.5.1 was given for
a sequenceR 1 ;R 2 ;::: of pairwise independent random variables with the same
mean and variance.
The theorem generalizes straighforwardly to sequences of pairwise independent
random variables, possibly withdifferentdistributions, as long as all their variances
are bounded by some constant.

Theorem(Generalized Pairwise Independent Sampling).LetX 1 ;X 2 ;:::be a se-
quence of pairwise independent random variables such thatVarŒXiçbfor some
b 0 and alli 1. Let

AnWWD

X 1 CX 2 C


CXn

n

;

nWWDExŒAnç:

Then for every > 0,

PrŒjAnnj> ç

b

^2

1

n

: (18.29)

(a)Prove the Generalized Pairwise Independent Sampling Theorem.

(b)Conclude that the following holds:
Corollary(Generalized Weak Law of Large Numbers).For every > 0,

n!1limPrŒjAnnjçD1:

Problem 18.14.
AnInternational Journal of Epidemiologyhas a policy of publishing papers about
drug trial results only if the conclusion about the drug’s effectiveness (or lack
thereof) holds at the 95% confidence level. The editors and reviewers carefully
check that any trial whose results they publish wasproperly performed and accu-
rately reported. They are also careful to check that trials whose results they publish
have been conducted independently of each other.