Discrete Mathematics for Computer Science

504 CHAPTER 8 Discrete Probability

Proof. The event E tl n E i2 n ... n E* 1kof the cross product sample space consists of all

n-tuples in Q1 x ... x Q,2 with entries in positions i1, i 2. ik that belong to the events

Eil ..., Eik Of Qil,.. I Qik, respectively.

We first define some terms to make it easier to express this set of n-tuples in the form

E 1 x E 2 X ... x E.

Let X = {il, i2 .... ik} and In = [1,2 ... , n}. Then for 1 < i < n, let

=Q2 fori E I, - X

Ei = IEim for i = im for some im E X

Since P(Ej) = 1 whenever Ej = "2j, the result follows from Theorem 3. U

We see the use of this corollary in the next example.

Example 7. Consider rolling a die three times, and choose a sample space 0 = Q1 x

Q2 X Q3 where Q1= = = Q3 = {1, 2, 3, 4, 5, 6}. What is the probability of getting an

odd number on the first roll and an even number on the third roll?

Solution. Consider E 1 = {1, 3, 5} C g21 and E 3 = {2, 4, 61 cE Qi 3 .In Q2, getting an odd

number on the first roll is the event E* = E 1 X Q22 X Q23; getting an even number on the

third roll is the event E* = Q, x ×2 x E 3 .Having both these events occur is the event

E* A E*. By Corollary 2 of Theorem 3,

P(E n E) = P(E^1 ) • P(E^3 ) = (3)(3) =

Alternatively, observe that EA * E* consists of 3 • 6 • 3 = 54 ordered triples in a sample

space of size 63 with a uniform probability density function and so has probability 54.

6-3 = 1/4. N

We began the study of cross product sample spaces by stating the Probability Multi-

plication Principle, which Theorem 3 justified mathematically. Corollary 2 to Theorem 3

can be viewed as justifying the extension of the Multiplication Principle from outcomes to

events. We now summarize the major results about Cross Product Events.

Probability of Cross Product Events

"* The probability of an event in cross product form E 1 x ... x En is the product of

the event probabilities

P(El x ... x E,) = P(EI)'". P (E,)

"* The simultaneous occurrence of k events E i,...., Ei in some k of the n sample

spaces composing a cross product can be regarded as a single event

Eýq n. .. n Ei* _C 0f1 x ... x i2n

"* The probability of this single event in Q1 x 22 x ... x Q, is the product of the

event probabilities P (Ei, ) ... P(Eik).