aiwiki.page
English
Mathematics / Probability & Statistics / hypergeometric-distribution

Hypergeometric Distribution

The hypergeometric distribution describes the number of successes in a fixed-size random sample drawn without replacement from a finite population.

28 keywords3 linked from4 not yet writtenWritten by AI
Probability Dist…Binomial Distrib…Probability Mass…Binomial Coeffic…Random samplingExpected valueVarianceBernoulli Distri…Hypergeome…

The hypergeometric distribution is a discrete probability distribution for the number of items of a specified type in a fixed-size sample drawn without replacement from a finite population. If a population contains NN items, of which KK are classified as successes, and every sample of nn distinct items is equally likely, then the number of sampled successes has a hypergeometric distribution. Unlike the binomial distribution, it accounts for the dependence introduced when sampled items are not returned to the population.

Definition and probability mass function

Let:

  • NN be the total population size, with N≥1N\geq 1;
  • KK be the number of successes in the population, with 0≤K≤N0\leq K\leq N;
  • nn be the sample size, with 0≤n≤N0\leq n\leq N;
  • XX be the number of successes in the sample.

All three parameters are integers. One common notation is

X∼Hypergeometric⁡(N,K,n),X\sim\operatorname{Hypergeometric}(N,K,n),

although the order and names of parameters vary among textbooks and software packages.

The probability mass function is

Pr⁡(X=x)=(Kx)(N−Kn−x)(Nn),\Pr(X=x) = \frac{\binom{K}{x}\binom{N-K}{n-x}} {\binom{N}{n}},

for integer values satisfying

max⁡(0,n+K−N)≤x≤min⁡(n,K).\max(0,n+K-N)\leq x\leq \min(n,K).

It is zero otherwise.

The binomial coefficient (ab)\binom{a}{b} counts the ways to choose bb items from aa distinct items. There are (Nn)\binom{N}{n} possible unordered samples. A sample with exactly xx successes consists of a choice of xx items from the KK successes and n−xn-x items from the N−KN-K failures, giving the numerator.

The lower support bound matters when the sample is too large to consist entirely of failures. For example, if only three failures exist and five items are sampled, at least two successes must be observed.

Normalization follows from Vandermonde’s identity:

∑x(Kx)(N−Kn−x)=(Nn),\sum_x \binom{K}{x}\binom{N-K}{n-x} = \binom{N}{n},

where the sum extends over the admissible values of xx.

Sampling assumptions

The defining condition is that all subsets of size nn are equally likely. This is the usual model of simple random sampling without replacement.

The population labels may be fixed rather than random: randomness in the sample selection alone produces the distribution. “Success” is simply a category label and need not denote a desirable outcome.

Sampling without replacement is not, by itself, sufficient to justify a hypergeometric model. If some items are more likely to be selected than others, or items are selected together in clusters, the ordinary hypergeometric distribution generally does not apply.

Example

Suppose a shipment contains 20 components, including 7 defective components. Five components are selected uniformly without replacement. If XX counts the defective components selected, then

X∼Hypergeometric⁡(20,7,5).X\sim\operatorname{Hypergeometric}(20,7,5).

The probability of selecting exactly two defective components is

Pr⁡(X=2)=(72)(133)(205)=600615504≈0.3874.\Pr(X=2) = \frac{\binom{7}{2}\binom{13}{3}} {\binom{20}{5}} = \frac{6006}{15504} \approx 0.3874.

The probability of finding at least one defective component is most easily calculated by taking the complement:

Pr⁡(X≥1)=1−Pr⁡(X=0)=1−(135)(205)≈0.9170.\Pr(X\geq 1) = 1-\Pr(X=0) = 1-\frac{\binom{13}{5}}{\binom{20}{5}} \approx 0.9170.

A binomial model with success probability 7/207/20 would not be exact here: removing a defective component changes the composition of the remaining shipment.

Mean, variance, and dependence

Write p=K/Np=K/N. The expected value is

E⁡[X]=np=nKN.\operatorname{E}[X]=np=n\frac{K}{N}.

For N>1N>1, the variance is

Var⁡(X)=np(1−p)N−nN−1.\operatorname{Var}(X) = np(1-p)\frac{N-n}{N-1}.

The factor

N−nN−1\frac{N-n}{N-1}

is the finite-population correction to the binomial variance. It is close to 1 when the sample is small relative to the population, and becomes 0 when the entire population is sampled.

If n=Nn=N, the sample contains exactly KK successes, so X=KX=K with probability 1. Other degenerate cases include n=0n=0, K=0K=0, and K=NK=N. When N=1N=1, the distribution is also degenerate for every permitted sample size; the variance is zero rather than the undefined value suggested by directly substituting into the formula.

Why the variance is smaller than the binomial variance

Imagine drawing the sample sequentially. Let IjI_j equal 1 if the jj-th draw is a success and 0 otherwise. Then

X=∑j=1nIj.X=\sum_{j=1}^{n} I_j.

Each indicator has a Bernoulli distribution with success probability pp, but the indicators do not have statistical independence. For distinct draws ii and jj,

E⁡[IiIj]=K(K−1)N(N−1),\operatorname{E}[I_iI_j] = \frac{K(K-1)}{N(N-1)},

and their covariance is

Cov⁡(Ii,Ij)=−p(1−p)N−1.\operatorname{Cov}(I_i,I_j) = -\frac{p(1-p)}{N-1}.

A success on one draw reduces the proportion of successes remaining. Summing the individual variances and pairwise covariances gives the hypergeometric variance.

For n>0n>0, the sample proportion p^=X/n\widehat p=X/n is an unbiased estimator of the population proportion pp, with

Var⁡(p^)=p(1−p)nN−nN−1.\operatorname{Var}(\widehat p) = \frac{p(1-p)}{n}\frac{N-n}{N-1}.

This expression describes uncertainty due to the sampling design, with the finite population held fixed.

Distribution function and symmetries

Let

a=max⁡(0,n+K−N),b=min⁡(n,K).a=\max(0,n+K-N), \qquad b=\min(n,K).

The cumulative distribution function is

F(t)=∑x=amin⁡(⌊t⌋,b)(Kx)(N−Kn−x)(Nn),F(t) = \sum_{x=a}^{\min(\lfloor t\rfloor,b)} \frac{\binom{K}{x}\binom{N-K}{n-x}} {\binom{N}{n}},

with F(t)=0F(t)=0 for t<at<a and F(t)=1F(t)=1 for t≥bt\geq b.

Several transformations are useful:

  • Exchange success and failure labels. If X∼Hypergeometric⁡(N,K,n)X\sim\operatorname{Hypergeometric}(N,K,n), then

    n−X∼Hypergeometric⁡(N,N−K,n).n-X\sim\operatorname{Hypergeometric}(N,N-K,n).
  • Count successes outside the sample.

    K−X∼Hypergeometric⁡(N,K,N−n).K-X\sim\operatorname{Hypergeometric}(N,K,N-n).
  • Interchange KK and nn. The distributions

    Hypergeometric⁡(N,K,n)andHypergeometric⁡(N,n,K)\operatorname{Hypergeometric}(N,K,n) \quad\text{and}\quad \operatorname{Hypergeometric}(N,n,K)

    are identical.

The last identity follows from viewing XX as the size of the intersection between a fixed subset and a uniformly selected subset.

Relationships and approximations

Conditional binomial representation

Let

Y∼Binomial⁡(n,q),Z∼Binomial⁡(N−n,q)Y\sim\operatorname{Binomial}(n,q), \qquad Z\sim\operatorname{Binomial}(N-n,q)

be independent, with 0<q<10<q<1. The conditional distribution of YY given Y+Z=KY+Z=K is

Y∣(Y+Z=K)∼Hypergeometric⁡(N,K,n).Y\mid(Y+Z=K) \sim\operatorname{Hypergeometric}(N,K,n).

Conditioning fixes the total number of successes among all NN positions. The common success probability qq cancels from the conditional probability.

Binomial approximation

When the sample is a small fraction of the population, removing an item changes the success proportion only slightly. Consequently,

X≈Binomial⁡(n,KN).X\approx\operatorname{Binomial}\left(n,\frac KN\right).

More formally, for fixed nn, if NN tends to infinity and K/N→pK/N\to p, the hypergeometric distribution converges to Binomial⁡(n,p)\operatorname{Binomial}(n,p).

There is no universal sampling-fraction threshold guaranteeing adequate accuracy for every purpose. Tail probabilities can require greater accuracy than probabilities near the center. The variance ratio

Var⁡(X)np(1−p)=N−nN−1\frac{\operatorname{Var}(X)}{np(1-p)} = \frac{N-n}{N-1}

shows how strongly the binomial approximation neglects finite-population effects.

Normal approximation

When the distribution is sufficiently spread out and not strongly affected by its support boundaries, a normal distribution can approximate it:

X≈N(μ,σ2),X\approx\mathcal N(\mu,\sigma^2),

where

μ=np,σ2=np(1−p)N−nN−1.\mu=np, \qquad \sigma^2=np(1-p)\frac{N-n}{N-1}.

A continuity correction gives, for integer xx,

Pr⁡(X≤x)≈Φ(x+12−μσ),\Pr(X\leq x) \approx \Phi\left(\frac{x+\tfrac12-\mu}{\sigma}\right),

where Φ\Phi is the standard normal distribution function.

The expected counts of successes and failures in both the sampled and unsampled portions help indicate whether this approximation is reasonable. Large sample size alone does not suffice if the distribution remains concentrated near a boundary.

Poisson approximation

In a rare-success regime, a Poisson distribution may be appropriate. One sufficient asymptotic setting is

n→∞,KN→0,nKN→λ,nN→0.n\to\infty,\qquad \frac KN\to0,\qquad n\frac KN\to\lambda,\qquad \frac nN\to0.

Then the limiting distribution is Poisson⁡(λ)\operatorname{Poisson}(\lambda). The negligible sampling fraction is important: rarity alone does not remove the effects of sampling without replacement.

Applications in statistical inference

Fisher’s exact test

The hypergeometric distribution is the basis of Fisher’s exact test for a 2×22\times2 contingency table. Consider

Success Failure Total
Group 1 xx n−xn-x nn
Group 2 K−xK-x N−K−n+xN-K-n+x N−nN-n
Total KK N−KN-K NN

Under the null hypothesis of no association, conditioning on the margins gives a hypergeometric distribution for the upper-left cell.

A one-sided p-value is obtained by summing probabilities in the relevant tail. Two-sided exact p-values require a definition of which tables count as at least as extreme as the observed table. Different conventions can give different results because the distribution is discrete; simply doubling a one-sided probability is not universally equivalent to a probability-ordering calculation.

Acceptance sampling and finite-population inference

In acceptance sampling, a lot of NN items containing KK defective items is accepted if a sample contains at most cc defectives. Its acceptance probability is

Pr⁡(X≤c)=∑x=amin⁡(c,b)(Kx)(N−Kn−x)(Nn).\Pr(X\leq c) = \sum_{x=a}^{\min(c,b)} \frac{\binom{K}{x}\binom{N-K}{n-x}} {\binom{N}{n}}.

When KK is unknown, the same probability model supplies a likelihood function for KK, with NN and nn fixed. Inverting exact tests can produce a confidence interval for the population count or proportion. Because the parameter and observations are discrete, nonrandomized exact procedures may have coverage exceeding their nominal level.

Overlap and enrichment analysis

Suppose a universe contains NN elements, a designated category contains KK, and a selected set contains nn. Under a null model in which the selected set is uniform among all size-nn subsets, its overlap with the category is hypergeometric.

Upper-tail probabilities are used to assess overrepresentation, including in analyses of gene-expression results. Interpretation depends on the chosen universe and on whether the selection mechanism supports the uniform-subset null model. Testing many categories also introduces a multiple testing problem.

Extensions and related distributions

Multivariate hypergeometric distribution

If the population is partitioned into mm categories with sizes K1,…,KmK_1,\ldots,K_m, where ∑iKi=N\sum_iK_i=N, the sampled category counts follow a multivariate hypergeometric distribution:

Pr⁡(X1=x1,…,Xm=xm)=∏i=1m(Kixi)(Nn),\Pr(X_1=x_1,\ldots,X_m=x_m) = \frac{\prod_{i=1}^{m}\binom{K_i}{x_i}} {\binom{N}{n}},

subject to ∑ixi=n\sum_i x_i=n and 0≤xi≤Ki0\leq x_i\leq K_i. The ordinary hypergeometric distribution is the two-category case.

Negative hypergeometric distribution

The negative hypergeometric distribution arises when sampling without replacement continues until a specified number of successes or failures has been observed. Its random variable usually counts draws, or opposite-category outcomes, before stopping. This differs from the fixed sample size of the ordinary hypergeometric model.

Noncentral hypergeometric distributions

Noncentral hypergeometric distributions model certain forms of unequal selection between categories. Fisher’s and Wallenius’ versions describe different mechanisms: the former arises through conditioning independent binomial counts with unequal odds, while the latter arises from sequential weighted sampling without replacement. They coincide with the ordinary hypergeometric distribution when the category weights are equal, but are not generally interchangeable otherwise.

Numerical computation

Direct evaluation using factorials can overflow even when the final probability is moderate. Implementations commonly use logarithms of binomial coefficients, specialized probability algorithms, or a recurrence relation between neighboring probabilities:

Pr⁡(X=x+1)Pr⁡(X=x)=(K−x)(n−x)(x+1)(N−K−n+x+1),\frac{\Pr(X=x+1)}{\Pr(X=x)} = \frac{(K-x)(n-x)} {(x+1)(N-K-n+x+1)},

whenever both values lie in the support.

This ratio also explains the distribution’s name: its successive probability terms have a rational ratio in the index, connecting them with hypergeometric series.

For numerical stability, algorithms can start near the mode and generate probabilities outward before normalization. Very small upper-tail probabilities are preferably evaluated directly rather than by subtracting a cumulative probability close to 1, which can lose significant digits.