Discrete Mathematics for Computer Science

488 CHAPTER 8 Discrete Probability

Now that we have derived an expression for P(E), how do we evaluate it? Trying to

compute n! or 365' or C(365, n) for other than the first few values of n involves numbers

that are huge. However, this difficulty can be avoided by noting that the expression for

P (E) can be rewritten

365 ) (364)] (363). (365 -n+ 1

35 \365J \365J 365

Using a calculator, it is easy to compute that for n > 23, P(E) < 0.5 and P(E) > 0.5. In

other words, if at least 23 students are in a class, then the chances are greater than 50% that

some two or more of them have the same birthday. 0

These examples have illustrated two ideas that aid in computing the probabilities of

events, which we now highlight.

Aids to Computing the Probability of Events

"* Set theory can be used to rewrite events in terms of other events. The Additive

Principle of Disjoint Events and Theorem 1 in Section 8.1.6 apply this idea.

"* The probability of the complement E of an event E can be used to determine the

probability of E, since by Theorem 2 in Section 8.1.6,

P(E) = 1 - P(E)

U Exercises

1. Suppose that Q2 is a sample space with a probability density function p and that
   E C __.

(a) Prove that 0 < p(E) < 1.

(b) What is the probability of the singleton event E = {[w}?

(c) What is the probability of the event E = Q?

2. Suppose that sample space ý21 is chosen to model the experiment of rolling a pair
   of dice and that the probability density function p assigned to 01 is p(0)) = 1/36
   for w e Q]. Under these assumptions, compute the probability of rolling a sum of
   3. Compare your answer to the answers of 1/18 and 1/11 obtained in the text, and
   discuss.


3. Consider a sample space Q consisting of five outcomes:

{0)1, 02, W03, 0)4, 605)

Which (if either) of the following functions pl and P2 can be probability densities on

QŽ? Explain your answer.