Discrete Mathematics for Computer Science

Cross Product Sample Spaces 501

(Inductive step) Suppose that the statement is true for n = k. Now, prove that it is true for
n = k + 1. Let p denote the usual probability density function on Q21 X Q22 X ... X Qn
(see Definition 2 in Section 8.3.2). Then,

P(Ex E2 x ... x Ek+l) -p (l, 02," ",ok+l)

• P (WO) P2((02) ... Pk+1 (O~k+1)

where the sums are taken over all combinations of choices of the coi from the Ei.
Rearranging terms so that all terms with the same choice for Wk+a from Ek+l are
grouped together yields

P(E x E 2 X ... x Ek+0i ( P1(Wk+1))(ZP1 A I ((W0)P2 (W2 ...Pk((Dk))

(Ok+lEEk+l,

where the second sum on the right-hand side is over all combinations of choices of the wi
from the Ei for 1 < i < k.
The second sum represents the probability of the event E 1 x E 2 x ... x Ek in
the sample space Q^21 X 0i2 2 X ... X £Ž,k. By the inductive hypothesis, it is equal to

P(Ea)P(E 2 ) ... P(Ek). Thus, summing over the outcomes Wk+l in Ek+1 gives

P(E1 x E 2 x ... x Ek+l) = E Pk+l(Wk+l) • P(E1) • P(E2)" P(Ek)

(Ok+l EEk+I

= P(EI) • P(E2)"". P (Ek) Y, Pk+lI((ok+l1)

(Ok+IEEk+1

= P(E 1 ) • P(E 2 ) ... P(Ek). P(Ek+1)

Therefore, n + 1 E T, and the result follows by the Principle of Mathematical In-
duction. 0

Example 4. At the beginning of this section, we formulated the situation "an odd number
on the die and a red card" as an event E 1 x E 2 _ Q I X22 where E 1 was the event "an odd
number on the die" in 0 1 = {1, 2, 3, 4, 5, 6} and E 2 was the event "a red card" in 022 =

{1, 2,..., 52). Verify the conclusion of Theorem 3 in this case by computing P(E 1 x E 2 )

directly and comparing the result to P(E 1 ) • P(E 2 ).

Solution. Define E 1 x E 2 to be the event of f01 x Q22 defined as

El x E 2 = {(W1, (02) : wo1 is an odd number in 01 and w2 is a red card in Q22}

Each outcome (&)I, w2) in E 1 x E 2 has probability

p(Owl, O2) = pl(Ol) .p2(o2) = (-) (-)

Hence,

P(E 1 X E 2 ) - (E1 x E 2 1-- ( (3)(26) =