Discrete Mathematics for Computer Science

536 CHAPTER 8 Discrete Probability

Since there may be several pairs of values x1 e Qx 1 , and x2 E Qx 2 such that x1 • X2 = X,

we write this event as the disjoint union of other events in Q2. We do this as follows: For

each choice of Xl E Q^2 x, and X2 E nŽx 2 such that x1 • X2 = x, we put (XI = Xl, X 2 =

X2) C Q2 into the union:

(X1 "X 2 =x)= U (XI =X 1 , X 2 =x 2 )

X 1 X2=X

where the union is taken over all pairs x1 E n^2 X 1 and x2 E Qx 2 such that x1 x2 • = x. Since

the events in the union are disjoint,

pxx2(x) = P(X1=x1,X 2 =x 2 )

X1 *X2=X

where the sum is taken over all pairs Xl E ý^2 xl and x2 E Q^2 x 2 such that x12 = x. Be-

cause X 1 and X 2 are independent random variables, we can replace P(X1 = x1, X2 = x2)

by px, (xl) • Px 2 (x2) in this equation, giving

PXI'X 2 (X)= Y PXI(Xl)"PX 2 (X2)

X 1 "X2X

Then, substitute for Px 1 .x 2 (x) in the expression for E(XI • X 2 ) to get

E(X. -X2) = x px 1 (xl)"px 2 (X2)

XEQX 1 .X 2 X1 "X 2 =X

Y E X1X2"Px(X!)PX 2 (X2)

XEtX 1 .X 2 Xl "X2=X

This double sum consists of exactly one summand

Xl " X2 Px 1 (Xl) " pX 2 (X2)

for each choice of a pair x E Qix, and x2 E ý2x 2 since writing out the double sum arranges

the summands so that the ones for which xi • x2 has some particular value x are grouped

together. Now, consider the expression

( : X1 PxI (Xi)) ( E X2 'PX 2 (X2)) = E (XI) -E(X 2 )

XiJEXl X2EQŽX 2

When multiplied out, the expression on the left gives exactly the same set of summands.

Hence,

E(X 1 • X 2 ) = E(X 1 ) • E(X 2 ) U

Now, we use this theorem to derive another important property of independent random

variables.

Theorem 4. (Variance of the Sum of Independent Random Variables) Let

X 1 , X2. X, be independent random variables on a sample space QŽ. Then,

Var(Xi + X 2 +... -+- Xn)= I: Var(Xi)

Proof. We prove the statement for n = 2 and leave the proof by induction for n > 2 as an

exercise. Let A, = E(XI) and A2 = E(X 2 ). By Theorem 3(a) (Linearity of Expectation)