Discrete Mathematics for Computer Science

496 CHAPTER 8 Discrete Probability

where si E Si for i > 1. Note that the size of a cross product of finitely many finite sets is

I S1 X S2 X '' ..X S, I= I S1I -I'I 21 .'.IS.1

Definition 2. Let Ž 21, Q2, ..- , Q, be sample spaces endowed with probability den-

sity functions P1, P2 ... Pn, respectively. Then, the cross product sample space of

Q 1, f22,..., Q, is the cross product

Q1 X Q2 X ... X , = I{(0)1,(02,' (,On) : 0)i E 2i for < i < n}

endowed with the probability density function p defined by

P (0)1, (02. (-On) = P1 (CO)O P2 ((02)." P. ((On).

Theorem 1 proves that p is a legitimate probability density when n = 2. The fact that

p is a legitimate probability density function for n > 2 sample spaces can be proved by

induction on n. All the ideas needed for the proof are contained in the proof of Theorem 1.

Example 2. In the communication network shown in Figure 8.2, each link may be up

or down. Assuming that the nodes connecting the links are always functioning and that

failures of the links are not related, what is the probability that a functioning set of links is

connecting node A to node C?

iLink functions

withprobability B Lik fcthpob

0.9 witha probability

Link functions

with probability

0.5

Figure 8.2 Communication network.

Solution. This situation can be modeled by a cross product sample space. Let Q^2 , = {0,

1) represent the status of link AB, where 0 means down and 1 means up. Similarly, let

Q22 and Q23 be sample spaces representing the status of link BC and the status of link AC,

respectively. Define the probability density functions on these sample spaces as shown in

Table 8.1.

The cross product sample space Q2 1 x Q22 X Q23 consists of eight 3-tuples of O's and

I's. These 3-tuples represent all possible combinations of the link conditions. For example,