Discrete Mathematics for Computer Science

522 CHAPTER 8 Discrete Probability

8.72 The Binomial Distribution

A distribution is simply a density that arises in a special way-that is, from a random

variable. Several distributions occur so frequently in applications that they have been given

special names. Let us look at a few examples.

Suppose a coin is flipped n times where the probability of heads is p and the prob-

ability of tails is q =^1 - p. We consider the usual sample space^02 consisting of the 2n

possible sequences of heads and tails. Suppose a random variable X is defined on Q by set-

ting X (co) equal to the number k of times heads occurs in the n-tuple (0 where 1 < k < n.

Then, the range f^2 x of X is {0, 1 ... n}, and the distribution px of X is given by

px(k) = C(n, k) -pk. (I - p)n-k for k = 0, 1 ... , n

This distribution is called the binomial distribution, and X is said to be binomially dis-

tributed.

Notice that the value of the binomial distribution for a particular k depends on n and

p as well as on k.

Definition 3. The binomial distribution is the probability density function defined on

{0, 1. n} by assigning to k = 0, 1 ..... n the value

b(k; n, p) = C(n, k) .pk .(I -- p)n-k

The binomial distribution gets its name from the fact that the Binomial Theorem can

be used to prove it is a valid density function. (The reader should try this.) The binomial

distribution is generally thought of as arising from a random variable X that counts suc-

cesses (or failures) for n independent repetitions of a two-outcome experiment. Certainly,

however, nothing is wrong with assigning a density p(k) = b(k; n, p) to the sample space

{0, 1, ... , n} without thinking of a random variable. Use of the term distribution instead of

probability density simply indicates that we have a random variable in mind.

The value b(k; n, p) of the binomial distribution has another interpretation: It is the

probability of getting exactly k red balls if we draw a ball n times from an urn in which the

proportion of red balls is p and we replace the ball after each draw.

8.73 The Hypergeometric Distribution

A second important distribution can be motivated by the process of drawing balls from an

urn repeatedly without replacing a ball after it is drawn. Suppose an urn contains m balls,

of which r are red and the rest are black. Thus, there are m - r black balls. We will draw

n balls where n < m, without replacing them. If we do not replace the ball each time, then

the probability of getting a red ball on a particular draw depends on what happened on

previous draws. To calculate the probability that we will draw exactly k red balls (and,

hence, exactly n - k black balls), imagine that we pick a handful of n balls from the urn all

at once where each such handful is equally likely. We choose the sample space 0? to be the

set of all possible handfuls of n balls, so each element of 0Ž is actually a set of n balls. We

put a uniform density on 02 that consists of C(m, n) outcomes. Now, let a random variable

X be defined on 2 as follows:

X (co) = the number of red balls in wo