Discrete Mathematics for Computer Science

500 CHAPTER 8 Discrete Probability

Theorem 2. (Probability of k Successes in a Bernoulli Process) The function

p(wk) = b(n; k, p) defines a probability density function on

0 ={[W0,W01, 02.W-- -(0

Proof Clearly, b(n; k, p) > 0 for 0 < k < n. To prove that

L b(n;k,p)=I

O<k<n

substitute in the values of b(n; k, p):

1 b(n; k, p) = C(n, 0) p qn + C(n, 1) p'qn-1 + + C(n, n) pnq0

0<k<n

By the Binomial Theorem (see Section 7.9.1), the right side is (p + q)n. Since p + q = 1,

the result follows.

8.3.4 Events of Cross Product Form

We now leave the special case of Bernoulli processes and return to cross product sample

spaces in general.

Many events in cross product sample spaces are cross products of events in the individ-

ual sample spaces. Suppose we roll a die and pick a card from a shuffled deck, associating

with these experiments the sample spaces

f21={1,2,3,4,5,61 and QŽ2={1,2,3 ... , 51,52}

with uniform probability densities. The combined experiment has an associated sample

space Q^21 x Q22. Let El C QŽ1 be the event "an odd number shows on the die," and let

E2 _ Q 2 be the event "a red card is drawn." Then, E 1 x E 2 _^21 x 02 is the event "an

odd number on the die and a red card." (In the context of cross product events such as this,

we will use Ei to denote an event in "i.)

In the die-and-card example, the roll of the first die has no connection to the selection

of the card, so it seems to be reasonable that P(El x E 2 ) should be P(E 1 ) • P(E 2 ). How-

ever, we are not at liberty to assign probabilities to events. Once probabilities have been

assigned to the individual outcomes in a sample space, the probability of an event, by def-

inition, must be computed by summing the probabilities of the outcomes in the event. The

next theorem shows that the probabilities of events having a cross product form do, indeed,

obey a multiplication rule, just as we have speculated for this die-and-card situation.

Theorem 3. (Probability of Events of Cross Product Form) In a cross product sam-

ple space QŽ I X22 x ... x Q, any event of the form E 1 x E 2 x ... x En has probability

P(E1x PE x E2 X x.~n= ... x En,) P(Ei)P(Ei

where Ei is an event in Qi for I < i < n.

Proof The proof is by induction on n. Define

T = {n E N: P(El x E 2 x ... x En) =HP(Ei)}

(Base step) The statement is trivially true for n = 1, so 1 e T.