Discrete Mathematics for Computer Science

484 CHAPTER 8 Discrete Probability

Example 9. Suppose the analysis of a sorting algorithm shows that the worst case (the

one requiring the most comparisons of names) occurs when the input data lists the names

in reverse order. What is the probability that this occurs if there are n names? Assume that

all orderings of the names are equally likely.

Solution. There are n! permutations of the names. These make up a sample space Q2.

Assuming that each permutation is equally likely to occur implies that the probability of

reverse order is just (I/n!). M

Example 10. Suppose that incoming computer mail messages are equally likely to be

addressed to user 1, 2, or 3. Three messages are received for delivery to these users. What

is the probability that no two messages are addressed to the same person?

Solution. The sample space should reveal all the ways the messages can be addressed.

This can be done by choosing

S= {(UI, U2, U3) 1 < Ul, U2, U3 < 31

Here, ui is the user to whom message i is addressed. The sample space consists of^33

outcomes, which we assume are equally likely. The event E (that no two messages go to

the same user) consists of all 3-tuples that are permutations of (1, 2, 3). There are 3! of

these, so P(E) = (3!)(3-3) = 2/9. M

Example 11. Suppose in the previous example that there are three messages and five

users. What is the probability that no two messages go to the same person?

Solution. Now, Q2 has size 53. However, E no longer consists of permutations of (1,

2, 3). Instead, it consists of permutations of the elements in sets of the form {ui, uj, U•}

where ui, u j, Uk are three distinct integers chosen from {1, 2, 3, 4, 5). There are C(5, 3)

choices for a set {ui, uj, Uk}, and there are 3! ways to permute the elements of a given

three-element set. Therefore, P(E) = C(5, 3)(3!)(5-3) = 12/25. U

Event Probabilities Under Uniform Density

To calculate the probability of an event E when the sample space Q has been assigned

a uniform probability density function:

1. Use counting techniques to determine I EI and 12 1.

2. Compute P(E) = E E I/1 2 I.

8.1.6 Set Theory and the Probability of Events

The sample spaces in Examples 6 through 11 were chosen to make it easy to formulate the

situations of interest as events-that is, as subsets of the sample spaces. The combinato-

rial counting techniques of Chapter 7 were then used to determine the number of elements

in those subsets. For finite sample spaces with uniform probability densities, this essen-

tially determines the event probabilities. This section shows that the operations on sets