Discrete Mathematics for Computer Science

Cross Product Sample Spaces 499

Example 3. Consider an n-trial Bernoulli process where each trial has a probability of

success p and a probability of failure q = 1 - p. What is the probability of obtaining

exactly k successes in a run of n trials?

Solution. A sample space for the entire process can be obtained by taking the cross prod-
uct of n copies of the sample space for a single trial. In other words, the sample space
consists of the 2' possible sequences of successes and failures. Each outcome in the event
"exactly k successes" consists of a sequence of k successes and n - k failures arranged in
some order (see Figure 8.4).

(0,0,0,0,0) (0,1,0,0,0) (1,0,0,0,0) (1,1,0,0,0)

(0,0,0,0,1) (0,1,0,0,1) (1,0,0,0,1) *(1,1,0,0,1)

(0,0,0,1,0) (0,1,0,1,0) (1,0,0,1,0) *(1,1,0,1,0)

(0,0,0, 1, 1) *(0,1,0,1,1) *(1,0,0,1,1) (1, 1,0, 1,1)

(0,0,1,0,0) (0,1,1,0,0) (1,0,1,0,0) *(1,1,1,0,0)

(0,0,1,0,1) *(0,1,1,0,1) *(1,0,1,0,1) (1,1,1,0,1)

(0,0,1,1,0) *(0,1,1,1,0) *(1,0,1,1,0) (1,1,1,1,0)

(0,0,1,1,1) (0,1,1,1,1) (1,0,1,1,1) (1,1,1,1,1)

Figure 8.4 Bernoulli trial process for n = 5.

The outcomes in the event "exactly three successes in five trials" are indicated by
an asterisk in Figure 8.4. The probability of any single such outcome, regardless of the
ordering of successes and failures, is pkqn-k. There are C(n, k) orderings, because choos-
ing the positions for the k successes determines the positions for the failures. Hence, the
probability of the event "exactly k successes" is C(n, k) • pkqn-k. 0

Notation. In an n-trial Bernoulli process with probability p of success on each trial, the
probability of exactly k successes is denoted b(n; k, p).

Probability of k Successes in a Bernoulli Process

The probability of exactly k successes in an n-trial Bernoulli process with probability

p of success on each trial is

b(n; k, p) = C(n, k) pkqn-k

where0<p< I and q= 1-p.

Suppose that in an n-trial Bernoulli process we are interested exclusively in events of
the form "exactly k successes" for various values of k. Then, there is an alternative to the
cross product sample space-namely, a sample space with outcomes that correspond to the
occurrence of exactly k successes: Q2 = {[oC, W1, • • •, (On} where outcome (Ok means "ex-
actly k successes" for 0 < k < n. Since the probability of the event "exactly k successes" in
the cross product sample space is b(n; k, p), it seems to be reasonable to define a probabil-
ity density function on the alternative sample space Q2 by setting P(wok) = b(n; k, p). The
following theorem verifies that this is, indeed, a legitimate probability density function.