Discrete Mathematics for Computer Science

534 CHAPTER 8 Discrete Probability

form an independent set. In other words (recall Definition 2 of Section 8.5.1:

P(X 1 = X 1 , X 2 X2- ..... X = X) = H P(Xi = xi)

Example 3. Suppose we toss a fair penny and a fair nickel. The associated sample space

Qa consists of four ordered pairs, each having probability 1/4. Let us define random vari-

ables X 1 and X 2 on Qa by

X (0)= 1 if the coins agree

I -1 otherwise

X 2 ((w) the number of heads in outcome a)

Are X 1 and X 2 independent?

Solution. First, we compute the probability distributions induced on x= {1-1, 11 and

fax 2 = {0, 1, 2):

1

PX 1 ) = px 1 (-1) =

1

px 2 (O) = -

1

Px 2 (1) =

Px 2 (^2 ) =^1

There are 2. 3 = 6 ways to choose xj E fax 1 and x2 E• fx 2 .If XI and X 2 were indepen-

dent, we would have to prove it by verifying that for each of the six combinations of xI

and X2 the events (XI = xj) and (X 2 = x2) are independent. However, X1 and X 2 are not

independent. To prove this requires only that we find one case for which the formula in

Definition 2 of Section 8.5.1 does not hold. Consider xj = 1 and x2 = 2. The event

(X 1 = 1, X 2 = 2) = {(heads, heads))

has probability 1/4. On the other hand,

1 1

P(Xi = 1)=px,(l)= - and P(X 2 =2)=Px 2 (2)-

2 4

Hence, the random variables X 1 and X 2 are not independent:

1 1

P(X 1 = 1, X 2 = 2) = A # P(XI = 1). P(X 2 = 2)

48

Definition 4. Let X 1 , X 2 ... , Xn be random variables defined on the same sample space

Qa. Then X 1 , X 2 ... , Xn are said to be independent, identically distributed (i.i.d.) ran-

dom variables if and only if

(a) X 1 , X 2 ... , X, are independent.

(b) X 1 , X 2 ,..., X, have the same range axj .... QX,, denoted fQx.

(c) X 1 , X 2 .,.... X, induce on £^2 x the same distribution PXl ..... px,, denoted px.