Discrete Mathematics for Computer Science

546 CHAPTER 8 Discrete Probability

(f) Describe in detail the event E C Q2 that at least one processor at each stage is up,

and write an expression for its probability. (You may use complements of events.)

2. Suppose we double the numbers of processors at each stage of the series-parallel sys-
   tem in Exercise 1. Compare the probability that a job makes it through the new system
   with the probability that a job makes it through the old system.


3. Suppose one of the processors of stage 4 in Exercise 1 is removed and put in parallel
   with the processor at stage 3. Now, stage 3 has two parallel processors, one of which
   has probability P3 of being up and the other of which has probability P4 of being up,
   and stage 4 has two parallel processors, each with probability P4 of being up. Answer
   parts (a) through (f) of Exercise 1 for this new system.


4. The probabilities of an event often can be evaluated by determining the probability
   density function and then summing it over the outcomes in the event. However, the
   theory developed in Section 8.5 often leads to simpler computations. This exercise
   illustrates the two approaches.
   Consider the nonseries-parallel system as shown:

nl n2

S < >t

n3 n4

The system works correctly provided at least one of the directed paths from s to t has

all its intermediate nodes working. For i = 1, 2, 3, and 4 let pi denote the probability

that node ni is working, and assume that the nodes function independently of one

another. Let W denote the event "the system works correctly." You will be asked to

describe the situation in terms of a cross product sample space

S= 01 X '22 X QiŽ 3 X 24

As usual, if Ei C Qi is an event in Qi, then E7 C Q2 denotes the corresponding event

in QŽ. Make sure to explain your answers.

(a) Let fj for i = 1, 2, 3, and 4 be the probability density function on Qi. Describe

the situation in terms of a cross product sample space:

Q = 1 X Q2 X Q3 X 24

Specify a legitimate probability density p on Q2 in terms of probability densities

fi on Qi. (Recall that pi is the probability that node ni works.)

(b) Describe the event "the system works correctly" as a subset W C 2, and give an

expression for P (W) by summing the probability density p you defined in part a

on the outcomes in W. This will be a little tedious, which is part of the point this

exercise illustrates.

(c) Let E* C Q_ denote the event that node ni works. How many outcomes of Q2 be-

long to Ei*?

(d) Compute P(E*) by using the theory of cross product sample spaces rather than

by summing p(a)) over (o c E7.