Discrete Mathematics for Computer Science

Cross Product Sample Spaces 493

should be (0.7) (0.4) = 0.28. Continuing in this way, we assign to each ordered pair of out-

comes the product of the corresponding probability densities. The tree diagram in Figure

8.1 enumerates the outcomes and computes their probabilities.

o ) p(O)

.25 busy (.3) (.25) =.075

busy free (.3) (.40) = .120

Shold (.3) (.35) = .105

0.7 .25 busy (.7) (.25) =.175

free free. (.7) (.40) = .280

hold (.7) (.35) = .245

1.000

Home Service

telephone number

status status

Figure 8.1 Tree diagram.

We have assigned probabilities based on an intuitive line of reasoning. Have we suc-
ceeded in defining a legitimate probability density function? The reader can check that we
have. 0

In the previous example, we multiplied the probabilities of outcomes from two unre-
lated experiments to obtain a probability for their combined outcome. This is an application
of what we call the Probability Multiplication Principle.

Probability Multiplication Principle

Multiplying together the probabilities of outcomes of unrelated experiments assigns

reasonable probabilities to the various combinations of outcomes.

In the Birthday Problem, the assignment of the uniform probability density func-
tion to the sample space consisting of 365' n-tuples can be viewed as a special case
of the Probability Multiplication Principle. On the one hand, we can reason as before:
Each n-tuple seems to be equally likely, so each should have probability

1

1/I 365n365n