Discrete Mathematics for Computer Science

Cross Product Sample Spaces 495

where w ranges over the outcomes (W0, w2) in 92. By definition of p, the left-hand side is

YE (pl((0l)'p2((02))

(W1l402) GO

This expression represents the sum of all possible products Pi (l0) • p2 (o02). The product

of F., p1(wo) with ZY-Ž2 P2(w), however, is the same quantity as the sum of all possible

products p I(w) • P2(w) by the Product of Sums Principle. Also, P1 and P2 are probability

densities on Q^2 , and 922, respectively, so

Y pl(w)= P2((02)^1

wIEl^21 W2EQ2

Hence,

Pw•• Ip (Ogl) -P2 (62)) = llpl (oil)) ,• P2((092))

-1.1

This completes the proof. U

8.3.2 The Cross Product of Sample Spaces

The sample space Q2 of Theorem 1, which is endowed with the probability density func-
tion p given by that theorem, is called a cross product sample space. This notation was
introduced in Section 1.3.4, but we recall it for convenience here. Such a sample space 92
is usually denoted 921 X 022 to indicate that it is based on the two sample spaces Q1 and
Q22. In fact, we can form a cross product sample space from any number n > 2 of sam-
ple spaces. This construction involves taking a cross product of sets, as defined below in
Definition 1, and then endowing this new set with a certain probability density, as given in
Definition 2.

Definition 1. The cross product of n sets

S 1 ,S 2. an

is the set of all n-tuples

(s1, S2. S)

where Si E Si for I <i <n.

Notation. The cross product of n sets is denoted as S1 x S2 x ... x Sn. When the sets
are all copies of the same set S, then the cross product is denoted Sn.
The cross product of a countably infinite ordered list of sets

S1,$2 ....

is the set of all sequences

(sl,s2 ....)