Discrete Mathematics for Computer Science

Variance, Standard Deviation, and the Law of Averages 533

Proof. By definition,

or-2 = T-•(x(o) _- t)." P(CO)

Since the summands are all non-negative, the value of the sum certainly cannot increase if

we leave out some of its terms. In particular, let

A = {wo : IX(co) - Al > E}

and just sum over 60 E A. This gives

0,2 > X(w)- /)^2 _ p(w,)

wEA

>- E2P(ft))

(OEA

-= e^2 P(A)

= •2P(0 X - Al >_ E)

Hence,

O-^2

Next, we will use Theorem 2 to prove an important result-the Law of Averages.

8.9.2 Independent Random Variables

Suppose we run an experiment described by a sample space Q2, with random variables X 1

and X 2 defined on Q2. After the experiment produces some outcome (0 E Q, someone tells

us the value x1 = X 1 (w) without telling us the outcome wo. Does this help us to guess the

value x2 = X 2 (co)? The answer depends on what the random variables are. Knowing the

value of one may determine the value of the other for some outcomes in Q2. On the other

hand, knowing the value of one sometimes gives no information about the other. Of course,

the outcomes that give rise to the values xi for i = 1,^2 form events

{1 " Xi (w0) = xJi

in QŽ, so we are really asking whether those events are independent.

As usual, we denote events of the form

{fa : Xi(a)) = xi}

by (Xi = xi) where xi is some value in the range of Xi. We denote the event

{(0): Xl()) = X1. Xk(Wo) = Xk}

by (X1 = X.. Xk = Xk).

Definition 3. Let X 1 , X 2 ,..., X, be random variables defined on a sample space Q2 en-
dowed with probability density p. Then, X 1 , X2 .... , X, are said to be independent ran-
dom variables if and only if for every choice of XI, x2. x, such that xi is contained in
the range of Xi for i = i, 2 .... n, the events

(XI = Xl), (X 2 = X2). (Xn = Xn)