Ferkans — Interactive Telecom Tutor

From Counting to Distribution

In Chapter 2 we derived the hypergeometric coefficient $\binom{K}{k}\binom{N-K}{n-k}/\binom{N}{n}$ as the probability of drawing exactly $k$ "successes" from a finite population. Now we study this formula as a full-fledged probability distribution and compare it to the binomial. The key question is: when does sampling without replacement behave like sampling with replacement?

Definition:
Hypergeometric Distribution

Let a population of $N$ items contain $K$ "successes" and $N - K$ "failures." Draw $n$ items without replacement. The number of successes $X$ follows the hypergeometric distribution $X \sim \text{Hyp}(N, K, n)$ with PMF: $P(k) = \mathbb{P}(X = k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}, \qquad k \in \{\max(0, n-N+K), \ldots, \min(n, K)\}$

,

Theorem: Mean and Variance of the Hypergeometric Distribution

If $X \sim \text{Hyp}(N, K, n)$ , then: $\mathbb{E}[X] = n \cdot \frac{K}{N}, \qquad \text{Var}(X) = n \cdot \frac{K}{N} \cdot \frac{N-K}{N} \cdot \frac{N-n}{N-1}$

The mean is the same as for $\text{Bin}(n, K/N)$ — on average, the fraction of successes in the sample matches the fraction in the population. The variance is smaller by the factor $\frac{N-n}{N-1}$ , called the finite population correction. Sampling without replacement reduces variability because each draw constrains the next.

Proof

Indicator decomposition

Define $X_i = \mathbf{1}[\text{draw } i \text{ is a success}]$ for $i = 1, \ldots, n$ . Then $X = \sum_{i=1}^{n} X_i$ .

Compute the mean

By symmetry, $\mathbb{P}(X_i = 1) = K/N$ for every $i$ (each item is equally likely to be in any draw position). Thus: $\mathbb{E}[X] = \sum_{i=1}^{n} \mathbb{E}[X_i] = n \cdot \frac{K}{N}$

Compute the variance

$\text{Var}(X_i) = \frac{K}{N}\left(1 - \frac{K}{N}\right)$ . For $i \neq j$ : $\mathbb{E}[X_i X_j] = \mathbb{P}(X_i = 1, X_j = 1) = \frac{K}{N} \cdot \frac{K-1}{N-1}$ so $\text{Cov}(X_i, X_j) = \frac{K(K-1)}{N(N-1)} - \frac{K^2}{N^2} = -\frac{K(N-K)}{N^2(N-1)}$ .

Combine

$\text{Var}(X) = n \cdot \frac{K}{N}\cdot\frac{N-K}{N} + n(n-1)\left(-\frac{K(N-K)}{N^2(N-1)}\right) = n \cdot \frac{K}{N}\cdot\frac{N-K}{N}\cdot\frac{N-n}{N-1} \qquad \square$ $

,

Definition:
Finite Population Correction

The factor $\frac{N - n}{N - 1}$ appearing in the variance of the hypergeometric distribution is called the finite population correction (FPC). It satisfies:

FPC $= 1$ when $n = 1$ (single draw: same as binomial).
FPC $= 0$ when $n = N$ (full census: no variability).
FPC $\to 1$ as $N \to \infty$ with $n$ fixed (large population: approaches binomial).

In survey sampling, the FPC is applied whenever the sample constitutes more than about 5% of the population. For most wireless applications, the "population" of possible events is effectively infinite and the FPC is negligible.

Theorem: Hypergeometric-to-Binomial Approximation

Let $X_N \sim \text{Hyp}(N, K_N, n)$ where $K_N / N \to p$ as $N \to \infty$ . Then for every fixed $k \in \{0, 1, \ldots, n\}$ : $\mathbb{P}(X_N = k) \to \binom{n}{k} p^k (1-p)^{n-k}$ That is, $X_N$ converges in distribution to $\text{Bin}(n, p)$ .

When the population is much larger than the sample, whether we replace each drawn item or not makes negligible difference — the composition of the population barely changes between draws. This is why polls of 1,000 people can represent 300 million: the finite population correction is essentially 1.

Proof

Write the PMF as a ratio of falling factorials

$\mathbb{P}(X_N = k) = \binom{n}{k} \cdot \frac{K_N(K_N - 1)\cdots(K_N - k + 1)}{N(N-1)\cdots(N-k+1)} \cdot \frac{(N-K_N)(N-K_N-1)\cdots(N-K_N-n+k+1)}{(N-k)(N-k-1)\cdots(N-n+1)}$ $

Take the limit

As $N \to \infty$ with $K_N/N \to p$ , each ratio of the form $(K_N - j)/(N - i)$ converges to $p$ , and similarly $(N - K_N - j)/(N - i) \to 1 - p$ . There are $k$ factors converging to $p$ and $n - k$ factors converging to $1 - p$ : $\mathbb{P}(X_N = k) \to \binom{n}{k} p^k (1-p)^{n-k} \qquad \square$

,

Hypergeometric vs. Binomial

Property	$\text{Hyp}(N, K, n)$	$\text{Bin}(n, p)$ with $p = K/N$
Sampling	Without replacement	With replacement
Mean	$n K/N$	$np$
Variance	$np(1-p) \cdot \frac{N-n}{N-1}$	$np(1-p)$
Support	$\{\max(0, n-N+K), \ldots, \min(n,K)\}$	$\{0, 1, \ldots, n\}$
Independence of draws	No	Yes
Approximation	Approaches Bin as $N \to \infty$	Exact

Hypergeometric vs. Binomial PMF

Compare the hypergeometric PMF (sampling without replacement) to the binomial approximation (sampling with replacement). As $N$ grows with $K/N$ fixed, the two distributions become indistinguishable.

Parameters

N

(population size)50

K

(successes in population)15

n

(sample size)10

Example: Quality Control Inspection

A shipment of $N = 100$ components contains $K = 5$ defective ones. An inspector draws $n = 10$ components without replacement. What is the probability that the sample contains exactly 1 defective component? Compare with the binomial approximation.

Solution

Hypergeometric calculation

$\mathbb{P}(X = 1) = \frac{\binom{5}{1}\binom{95}{9}}{\binom{100}{10}}$ $Computing:$ \binom{5}{1} = 5 $, and evaluating the ratio numerically gives$ \mathbb{P}(X = 1) \approx 0.3394$.

Binomial approximation

With $p = K/N = 0.05$ : $\mathbb{P}(Y = 1) = \binom{10}{1}(0.05)^1(0.95)^9 \approx 0.3151$ .

Compare

The binomial underestimates the true probability by about 7%. The finite population correction factor is $(100-10)/(100-1) \approx 0.909$ , which is already quite close to 1 but not negligible for the variance. For $N = 10{,}000$ with $K = 500$ (same $p = 0.05$ ), the two answers would agree to four decimal places.

Example: Lottery Probability

In a lottery, 6 numbers are drawn without replacement from $\{1, \ldots, 49\}$ . What is the probability of matching exactly 3 of your 6 chosen numbers?

Solution

Set up as hypergeometric

The "population" is $N = 49$ numbers, of which $K = 6$ are "successes" (the winning numbers). We draw $n = 6$ , and we want $X = 3$ matches.

Compute

$\mathbb{P}(X = 3) = \frac{\binom{6}{3}\binom{43}{3}}{\binom{49}{6}} = \frac{20 \cdot 12341}{13983816} \approx 0.01765$ $ About 1 in 57 tickets matches exactly 3 numbers.

Why This Matters: Hypergeometric Distribution in Random Access

In grant-free random access for massive IoT, a base station allocates $N$ pilot sequences. If $K$ devices are active and each selects a pilot uniformly at random, the number of devices selecting a given subset of $n$ pilots follows a distribution closely related to the hypergeometric. When $N$ is large relative to $K$ , the binomial approximation is accurate, but in overloaded regimes ( $K \gg N$ ), the finite-population effects become significant and the hypergeometric model is more appropriate.

Common Mistake: Forgetting the Support Constraints

Mistake:

Writing $\mathbb{P}(X = k)$ for $k = 0, 1, \ldots, n$ without checking that $k \leq K$ and $n - k \leq N - K$ .

Correction:

The hypergeometric PMF is zero outside $\max(0, n - N + K) \leq k \leq \min(n, K)$ . Always verify the support before computing — especially when $n$ is close to $N$ .

Historical Note: Origins of the Hypergeometric Distribution

19th–20th century

The term "hypergeometric" dates to the early 19th century and reflects the connection to the hypergeometric series ${}_2F_1(a, b; c; z)$ . The PMF of the hypergeometric distribution can be expressed as a terminating hypergeometric series. The distribution itself was studied implicitly by Laplace and explicitly by the statistician Karl Pearson in the early 1900s, who used it as the exact model for Fisher's "Lady Tasting Tea" experiment — one of the founding examples of hypothesis testing.

Quick Check

When is the finite population correction factor exactly equal to 0?

When $n = 1$

When $N \to \infty$

When $n = N$

When $K = 0$

Correction:

When

n = N

Correct. FPC $= (N - N)/(N - 1) = 0$ . Drawing the entire population leaves no randomness: $\text{Var}(X) = 0$ .

hypergeometric distribution

The distribution of the number of successes in $n$ draws without replacement from a population of $N$ items containing $K$ successes: $\mathbb{P}(X = k) = \binom{K}{k}\binom{N-K}{n-k}/\binom{N}{n}$ .

finite population correction

The factor $(N - n)/(N - 1)$ by which the variance of the hypergeometric distribution is smaller than that of the corresponding binomial.

Related: hypergeometric distribution

binomial distribution

The distribution of the number of successes in $n$ independent Bernoulli trials with success probability $p$ : $\mathbb{P}(X = k) = \binom{n}{k} p^k (1-p)^{n-k}$ .

Key Takeaway

The hypergeometric distribution models sampling without replacement and has the same mean as the binomial but a smaller variance by the finite population correction factor $(N-n)/(N-1)$ . When the population $N$ is much larger than the sample $n$ , the two distributions are practically indistinguishable.

The Hypergeometric Distribution