Concept map / Hypergeometric distribution

Share

The hypergeometric distribution

Count marked cards in a sample drawn without replacement, compare it with the binomial, and see how the finite population correction narrows the spread.

1Draw cards without putting them back

A deck has N cards and K of them are marked. Draw n cards without putting any back, so every hand of n cards is equally likely. The number of marked cards in the hand has a hypergeometric distribution. Its probabilities come from the combinations on the counting page, and it is the without-replacement partner of the binomial count.

Does it matter whether each card goes back before the next draw? Change the deck and the sample size, compare the two sets of bars, and draw cards by hand to see the chance of a marked card move as the deck shrinks.

0.00.250.5012345ProbabilityMarked cards in the sample (k)
Without replacement (hypergeometric)With replacement (binomial)

Deck: 16 cards left, 6 marked (◆)

Sample: 0 of 5 drawn, 0 marked. Next card marked: 6 of 16 = 37.5%.

The deck has 16 cards, 6 marked (37.5%). A sample of 5 drawn without replacement holds on average 1.88 marked cards with variance 0.86. Drawing with replacement gives the same mean but variance 1.17. The ratio, (N − n)/(N − 1) = 0.73, is the finite population correction.

More controls

2Does keeping the cards out change the spread?

A deck has 20 cards and 10 are marked. You draw 10 cards. Compare drawing without replacement (keep each card out) with drawing with replacement (shuffle each card back in). How does the spread of the number of marked cards compare?

3Count the hands, then shrink the variance

Every hand of n cards is equally likely. Count the hands with exactly k marked cards and divide by the number of all hands. The variance is the binomial variance times a correction factor. Point at a term and the matching cards or bars in section 1 light up.

P(X=k)=(Kk)  (N−Kn−k)(Nn)P(X = k) = \frac{\htmlClass{term-mark}{\binom{K}{k}}\;\htmlClass{term-unmark}{\binom{N-K}{n-k}}}{\binom{N}{n}}

Now, at the most likely count k = 2: P(X = 2) = 15 × 120 / 4,368 = 0.412.

Var⁡(X)=n KN(1−KN)  N−nN−1\operatorname{Var}(X) = n\,\frac{K}{N}\Bigl(1-\frac{K}{N}\Bigr)\;\htmlClass{term-fpc}{\frac{N-n}{N-1}}

Now: 5 × 0.375 × 0.625 × 11/15 = 1.172 × 0.733 = 0.859. A card in your hand cannot be drawn again, so the hand drifts toward the deck's own share of marked cards.

4Check yourself

The tasks use the sliders and buttons in section 1 and tick themselves when you meet them.

  • With a sample of at least 2 cards, make sampling without replacement behave almost like sampling with replacement: get the correction (N − n)/(N − 1) above 0.95.Now: n = 5, (N − n)/(N − 1) = 0.73
  • Leaving at least one card in the deck and with some marked and some unmarked cards, make the variance without replacement at most half the variance with replacement.Now: 0.86 without, 1.17 with replacement
  • Draw cards one at a time until the chance that the next card is marked is higher than it was before the first draw. If the sample fills up first, put the cards back under More controls.Now: at the start 37.5%, 0 cards drawn

5Both counts in R

dhyper() takes the count, the number of marked cards, the number of unmarked cards and the sample size, in that order. The snippet uses this page’s default deck (16 cards, 6 marked, 5 drawn), prints both distributions, and checks the variances, 1.172 with replacement and 0.859 without, against 20,000 simulated samples.

Hypergeometric and binomial countsShow the code
# Deck of N = 16 cards, K = 6 marked, sample of n = 5
N <- 16; K <- 6; n <- 5
k <- 0:n

# dhyper(k, marked, unmarked, sample size)
without <- dhyper(k, K, N - K, n)
with <- dbinom(k, n, K / N)
round(rbind(k, without, with), 3)

# Same mean; the variance shrinks by (N - n) / (N - 1)
var_with <- n * (K / N) * (1 - K / N)
fpc <- (N - n) / (N - 1)
round(c(with = var_with, without = var_with * fpc), 3)

# Check by simulation: sample() draws without replacement
set.seed(16)
deck <- rep(c(1, 0), c(K, N - K))
marked <- replicate(20000, sum(sample(deck, n)))
round(c(mean = mean(marked), var = var(marked)), 3)

Uses base R only.

Drawing without replacement, in brief