Hypergeometric Distributions, introduction to probability lesson

A bag holds twelve labeled tokens, five blue and seven white, and three tokens are drawn without putting any back. After a blue draw fewer blue tokens remain, so the chance of blue on the next draw goes down, and after a white draw it goes up. The draws are dependent, so the binomial model, which needs independent trials, does not describe this sample exactly. This lesson counts samples directly to get the exact distribution of the number of blue tokens, finds which counts are possible, and measures how the dependence between draws changes the variance.

Key terms

Sampling without replacement

Definition A finite population is a set of $N$ distinct items, where $N$ is a positive integer. Here $K$ of the items are marked and $N - K$ are unmarked, with $0 \le K \le N$ . A sample of size $n$ , where $0 \le n \le N$ , is drawn uniformly without replacement if it consists of $n$ distinct items and each of the $\binom{N}{n}$ subsets of size $n$ has the same probability $1 / \binom{N}{n}$ . Drawing one item at a time, each time uniformly among the items still present, produces such a sample. Sampling with replacement instead returns each item before the next draw, so an item can be drawn more than once. When every draw is uniform over all $N$ items whatever the earlier draws were, the draws are independent.

In plain words Each item can be chosen at most once, and no group of $n$ items is favored over another. Labeling items that look alike keeps them distinct, so the equally likely samples can be counted with combinations.

Example For the twelve labeled tokens and a sample of three, there are $\binom{12}{3} = 220$ equally likely subsets, each with probability $\tfrac{1}{220}$ . Drawing tokens $2$ , $7$ and $9$ in any of the six possible orders gives the same subset, so samples are counted with combinations, not with ordered lists.

Hypergeometric distribution

Definition Let $X$ be the number of marked items in a uniform sample of size $n$ drawn without replacement from a population of $N$ items, $K$ of them marked. For every integer $x$ in the support of $X$ ,

P(X = x) = \frac{\binom{K}{x}\binom{N - K}{n - x}}{\binom{N}{n}},

because a sample with exactly $x$ marked items is a choice of $x$ of the $K$ marked items together with $n - x$ of the $N - K$ unmarked items, and all $\binom{N}{n}$ samples are equally likely. We say that $X$ has the hypergeometric distribution with parameters $N$ , $K$ and $n$ . With the convention $\binom{a}{b} = 0$ for an integer $b < 0$ or $b > a$ , the same formula gives $0$ at every integer outside the support.

In plain words Count the samples with the right mix of marked and unmarked items and divide by the number of all samples. Two binomial coefficients are multiplied because each choice from the marked group can be paired with each choice from the unmarked group.

Example For three tokens from the bag, exactly two blue tokens means two of the five blue and one of the seven white, so there are $\binom{5}{2}\binom{7}{1} = 10 \cdot 7 = 70$ favorable subsets and $P(X = 2) = \tfrac{70}{220} = \tfrac{7}{22}$ . The whole distribution, written over the common denominator $44$ , is below.

$x$	$0$	$1$	$2$	$3$
$P(X = x)$	$\tfrac{7}{44}$	$\tfrac{21}{44}$	$\tfrac{14}{44}$	$\tfrac{2}{44}$

The masses add to $\tfrac{44}{44} = 1$ .

Support of a hypergeometric count

Definition The support of a hypergeometric count $X$ with parameters $N$ , $K$ and $n$ is the set of integers $x$ with

\begin{aligned} x &\ge \max(0, n - (N - K)), \\[0.4em] x &\le \min(n, K). \end{aligned}

The upper bound holds because the sample has only $n$ items and the population has only $K$ marked ones. The lower bound holds because a count is never negative and only $N - K$ unmarked items exist, so a sample larger than $N - K$ must contain at least $n - (N - K)$ marked items. Every integer between the bounds has positive probability.

In plain words Before computing anything, check which counts are possible. A large sample from a population with few unmarked items is forced to contain marked ones, and the count can never exceed the number of marked items available.

Example For three tokens from the bag, the bounds are $\max(0, 3 - 7) = 0$ and $\min(3, 5) = 3$ , so all four counts $0$ to $3$ are possible. Now draw nine tokens. Only seven are white, so at least $9 - 7 = 2$ must be blue, and at most $5$ can be, so the support is $\{2, 3, 4, 5\}$ . For instance,

\begin{aligned} P(X = 2) &= \frac{\binom{5}{2}\binom{7}{7}}{\binom{12}{9}} \\[0.4em] &= \frac{10}{220} = \frac{1}{22}. \end{aligned}

A binomial model with $n = 9$ and $p = \tfrac{5}{12}$ would give positive probability to the impossible counts $0$ and $1$ , and also to $6$ through $9$ , more blue tokens than the bag holds. If all twelve tokens are drawn, the support is the single value $5$ .

Dependent draws

Definition Draw the sample one item at a time, each time uniformly among the items remaining, and for $j = 1, \dots, n$ let $I_j = 1$ if draw $j$ is marked and $I_j = 0$ otherwise. Then $X = I_1 + \dots + I_n$ . By symmetry $P(I_j = 1) = K/N$ for every position $j$ , and when $N \ge 2$ , for two different positions $j \ne l$ ,

\begin{aligned} &P(I_j = 1,\ I_l = 1) \\[0.4em] &\quad = \frac{K}{N} \cdot \frac{K - 1}{N - 1}. \end{aligned}

When $0 < K < N$ this differs from $(K/N)^2$ , so for $n \ge 2$ the indicators of different draws are dependent. When $K = 0$ or $K = N$ every indicator is constant. Linearity of expectation does not need independence, and it gives

E[X] = \frac{nK}{N}.

In plain words Each draw on its own is marked with probability equal to the population proportion $K/N$ . What changes from draw to draw is the conditional probability. A marked draw leaves fewer marked items for later draws, and an unmarked draw leaves the same number of marked items among fewer items, yet the expected count is the same as with replacement.

Example In the token bag the first draw is blue with probability $\tfrac{5}{12}$ . Given that it is blue, the second draw is blue with probability $\tfrac{4}{11}$ , and given that it is white, with probability $\tfrac{5}{11}$ . Unconditionally the second draw is blue with probability $\tfrac{5}{12} \cdot \tfrac{4}{11} + \tfrac{7}{12} \cdot \tfrac{5}{11} = \tfrac{55}{132} = \tfrac{5}{12}$ . The color order blue, blue, white has probability $\tfrac{5}{12} \cdot \tfrac{4}{11} \cdot \tfrac{7}{10} = \tfrac{7}{66}$ , and the orders blue, white, blue and white, blue, blue have the same probability, so $P(X = 2) = 3 \cdot \tfrac{7}{66} = \tfrac{7}{22}$ , in agreement with the count of subsets. The mean is $E[X] = 3 \cdot \tfrac{5}{12} = \tfrac54$ . Three independent trials with success probability $\tfrac{5}{12}$ would describe drawing with replacement, not this sample.

Finite population correction

Definition For a hypergeometric count with $N \ge 2$ and $p = K/N$ ,

\begin{aligned} \operatorname{Var}(X) &= np(1 - p) \\[0.4em] &\quad \times \frac{N - n}{N - 1}. \end{aligned}

The factor $(N - n)/(N - 1)$ is the finite population correction, and $np(1 - p)$ is the variance of the count $\operatorname{Bin}(n, p)$ that sampling with replacement would give. The formula follows from the indicators. Since $I_j^2 = I_j$ , expanding $X^2$ gives $n$ single terms and $n(n - 1)$ cross terms, so

\begin{aligned} &E[X^2] = \frac{nK}{N} \\[0.4em] &\quad + \frac{n(n-1)K(K-1)}{N(N-1)}, \end{aligned}

and subtracting $(nK/N)^2$ and simplifying gives the formula. When $N = 1$ the count is constant, so its variance is $0$ and no correction is needed.

In plain words When $n \ge 2$ and $0 < K < N$ , the dependence between draws makes the count less variable than with replacement, because drawing a marked item makes later marked draws less likely and so tends to balance the sample. The correction equals $1$ when $n = 1$ and $0$ when $n = N$ , since a sample of the whole population gives $X = K$ for certain. When the sample is a small fraction of a large population the factor is close to $1$ , and a binomial model may approximate well. The hypergeometric model is still the exact one, and how good the approximation is depends on the numbers and on the event asked about.

Example For three tokens from the twelve, $p = \tfrac{5}{12}$ and

\begin{aligned} \operatorname{Var}(X) &= 3 \cdot \tfrac{5}{12} \cdot \tfrac{7}{12} \cdot \tfrac{9}{11} \\[0.4em] &= \tfrac{105}{176} \approx 0.597. \end{aligned}

With replacement the variance would be $3 \cdot \tfrac{5}{12} \cdot \tfrac{7}{12} = \tfrac{35}{48} \approx 0.729$ , and the ratio of the two is the correction $\tfrac{9}{11}$ .

Check yourself

A box holds nine labeled items, three of them marked. Two items are drawn uniformly without replacement. Find the probability of exactly one marked item and the probability of at least one.

Show the answer

There are $\binom{9}{2} = 36$ equally likely samples. Exactly one marked item means one of the three marked and one of the six unmarked, so there are $3 \cdot 6 = 18$ favorable samples and $P(X = 1) = \tfrac{18}{36} = \tfrac12$ . No marked item happens in $\binom{6}{2} = 15$ samples, so

P(X \ge 1) = 1 - \frac{15}{36} = \frac{7}{12}.

In the same setting, find $E[X]$ and $\operatorname{Var}(X)$ , and compare the variance with the one for two draws with replacement.

Show the answer

With $N = 9$ , $K = 3$ , $n = 2$ and $p = \tfrac13$ , the mean is $E[X] = 2 \cdot \tfrac13 = \tfrac23$ . The correction is $\tfrac{9 - 2}{9 - 1} = \tfrac78$ , so

\begin{aligned} \operatorname{Var}(X) &= 2 \cdot \tfrac13 \cdot \tfrac23 \cdot \tfrac78 \\[0.4em] &= \tfrac{7}{18}. \end{aligned}

With replacement the count would be $\operatorname{Bin}(2, \tfrac13)$ with variance $\tfrac49 = \tfrac{8}{18}$ , which is larger. As a check, the distribution is $P(X = 0) = \tfrac{5}{12}$ , $P(X = 1) = \tfrac12$ and $P(X = 2) = \tfrac{1}{12}$ , which gives the same mean and $E[X^2] - (E[X])^2 = \tfrac56 - \tfrac49 = \tfrac{7}{18}$ .

Now seven of the nine items are drawn without replacement. Someone uses the binomial model $\operatorname{Bin}(7, \tfrac13)$ and reports that no marked item appears with probability $(\tfrac23)^7 \approx 0.059$ . Find the support and the correct distribution of the number of marked items.

Show the answer

Only six unmarked items exist, so a sample of seven contains at least $7 - 6 = 1$ marked item, and at most $\min(7, 3) = 3$ . The support is $\{1, 2, 3\}$ and the probability of no marked item is $0$ . With $\binom{9}{7} = 36$ samples,

\begin{gathered} P(X = 1) = \tfrac{3 \cdot 1}{36} = \tfrac{1}{12}, \\[0.4em] P(X = 2) = \tfrac{3 \cdot 6}{36} = \tfrac{1}{2}, \\[0.4em] P(X = 3) = \tfrac{1 \cdot 15}{36} = \tfrac{5}{12}. \end{gathered}

The masses add to $1$ . The binomial model describes drawing with replacement, where the same item can be drawn more than once, so it gives positive probability to counts that cannot occur here, $0$ as well as $4$ through $7$ .

Hypergeometric Distributions

Key terms

Sampling without replacement

Hypergeometric distribution

Support of a hypergeometric count

Dependent draws

Finite population correction

Check yourself

How this lesson connects

Builds on

Where this leads in Statistics