Discrete Mathematics for Computer Science

Discrete Random Variables 523

Hence, X is a function from 02 to {0, 1, 2. n}. The probability in Q? of the event (X = k)

is computed as follows: The number of handfuls that contain k red balls (and n - k black

balls) is C(r, k) • C(m - r, n - k), because there are C(r, k) ways to choose k red balls

from the total number r of red balls and C(m - r, n - k) ways to choose n - k black balls

from the total number m - r of black balls. Since i has size C(m, n), the probability of

each handful is 1/C(m, n). Hence, the probability P(X = k) of obtaining exactly k red

balls, which is the summation of po(w) over all (o containing exactly k red balls, is

P(X = k) C(r,k).C(m - r, n - k)

C(m, n)

Since P(X = k) depends on n, r, and m as well as on k, we will denote P(X = k) by

h(k; n, r, m).

Definition 4. For integer parameters k, n, r, and m satisfying 0 < k < n < m and

k < r, the hypergeometric distribution is the probability density function defined on

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

h(k; n, r, m) - C(r, k) • C(m - r, n - k)

C (m, n)

The following example will help clarify this discussion.

Example 3. Suppose that 25 of 1000 parts in a bin are defective. What is the probability

that a randomly chosen set of 10 parts contains at least one defective part? (The parts are

chosen without replacement.)

Solution. The probability can be obtained by subtracting from 1 the probability that none

of the 10 parts is defective. This latter probability can be expressed in terms of the hyper-

geometric distribution. We have m = 1000 parts (or balls in an urn), of which r = 25 are

defective (red). We draw a handful of n =^10 and ask for the probability that k =^0 are

defective. Hence,

P(0 defects) = h(0; 10, 25, 1000) = C(25,0).C(975,

10)

C(1000, 10)

This can be rewritten as

975.974... 966 10! 975 974 966

1. 10! 1000.999... 991 1000 999 991
   S0.7754

The probability of at least one defective part in a handful of 10 chosen at random is

therefore

P(at least 1 defect) = 1 - P(0 defects) = 1 - 0.7754 = 0.2246

When m, r, and m - r are large compared to n, the binomial density b(k; n, rim)

can be used to approximate h(k; n, r, in). This approximation is based on the fact that
the proportion of red balls changes very little as we make the first few draws. For the last
example, the binomial approximation to

h(k; n, r, m) = h(0; 10, 25, 1000)