Discrete Mathematics for Computer Science

494 CHAPTER 8 Discrete Probability

On the other hand, we can reason as follows: The probability that a person has a particular

birthday is 1/365, and if the birthdays of different people are unrelated, then according to

the Probability Multiplication Principle, the probability of any given sequence of n birth-

days is (1/3 6 5)n. The two lines of reasoning assign the same probability density function.

In practice, the Probability Multiplication Principle provides good estimates for the

frequencies of combined outcomes of unrelated experiments, so naturally, we want to use

it to assign probability densities. Before we do, however, we must first check that the

probability densities so obtained actually satisfy the two defining properties of a probability

density. This check is carried out in Theorem 1.

The Product of Sums Principle is a simple observation about algebra that will make

the proof of the theorem easier to follow. It is such a useful observation that it is worth

receiving special attention.

Product of Sums Principle

The product of k sums is the same as the sum of all possible products of k terms, with

each term of a product taken from a different sum.

For example, consider the following product of k = 2 sums:

(2 + 3 + 5)(4 + 9) = (2.4 + 2 -9 + 3 -4 + 3 .9 + 5 4 + 5 9)

The right-hand side is the sum of all possible products of pairs of terms, one from (2 +

3 + 5) and one from (4 + 9). Similarly,

Yai)( bj = ai .bj

i=1 =1 l<i<n l<j<m

The expression on the left-hand side is written in a factored form, whereas the expression

on the right-hand side is written in a "multiplied out" form. Both expressions represent the

same quantity.

Theorem 1. (Probability Density on a Cross Product Sample Space) Let 21 and ý22

be sample spaces with probability density functions p1 and P2, respectively. Let

Q = {(W01, U2) : W1 E Q, and 0) 2 E Q2)

For each co = (w01,0)2) C Q2, let

p(w) = PI (0I) " P2((02)

Then, p is a probability density function on Q2.

Proof. Certainly, p((O)w, U)2)) > 0 for each (0)1, 0)2) E Q2, because it is the product of

non-negative numbers. Therefore, it remains only to verify that

Y, P(O))

weQ2