Hypergeometric distribution

From Wikipedia, the free encyclopedia

Hypergeometric
Parameters	${\begin{aligned}N&\in \left\{0,1,2,\dots \right\}\\K&\in \left\{0,1,2,\dots ,N\right\}\\n&\in \left\{0,1,2,\dots ,N\right\}\end{aligned}}\,$
Support	$\scriptstyle {k\,\in \,\left\{\max {(0,\,n+K-N)},\,\dots ,\,\min {(K,\,n)}\right\}}\,$
pmf	${{{K \choose k}{{N-K} \choose {n-k}}} \over {N \choose n}}$
CDF	$1-{{{n \choose {k+1}}{{N-n} \choose {K-k-1}}} \over {N \choose K}}\,_{3}F_{2}\!\!\left[{\begin{array}{c}1,\ k+1-K,\ k+1-n\\k+2,\ N+k+2-K-n\end{array}};1\right]$
Mean	$n{K \over N}$
Mode	$\left\lfloor {\frac {(n+1)(K+1)}{N+2}}\right\rfloor$
Variance	$n{K \over N}{(N-K) \over N}{N-n \over N-1}$
Skewness	${\frac {(N-2K)(N-1)^{{\frac {1}{2}}}(N-2n)}{[nK(N-K)(N-n)]^{{\frac {1}{2}}}(N-2)}}$
Ex. kurtosis	$\left.{\frac {1}{nK(N-K)(N-n)(N-2)(N-3)}}\cdot \right.$ ${\Big [}(N-1)N^{{2}}{\Big (}N(N+1)-6K(N-K)-6n(N-n){\Big )}+$ $6nK(N-K)(N-n)(5N-6){\Big ]}$
MGF	${\frac {{N-K \choose n}\scriptstyle {\,_{2}F_{1}(-n,-K;N-K-n+1;e^{{t}})}}{{N \choose n}}}\,\!$
CF	${\frac {{N-K \choose n}\scriptstyle {\,_{2}F_{1}(-n,-K;N-K-n+1;e^{{it}})}}{{N \choose n}}}$

In probability theory and statistics, the hypergeometric distribution is a discrete probability distribution that describes the probability of $k$ successes in $n$ draws without replacement from a finite population of size $N$ containing exactly $K$ successes. This is in contrast to the binomial distribution, which describes the probability of $k$ successes in $n$ draws with replacement.

Definition

The hypergeometric distribution applies to sampling without replacement from a finite population whose elements can be classified into two mutually exclusive categories like Pass/Fail, Male/Female or Employed/Unemployed. As random selections are made from the population, each subsequent draw decreases the population causing the probability of success to change with each draw.

The following conditions characterise the hypergeometric distribution:

The result of each draw can be classified into one or two categories.
The probability of a success changes on each draw.

A random variable $X$ follows the hypergeometric distribution if its probability mass function (pmf) is given by:^[1]

$P(X=k)={{{K \choose k}{{N-K} \choose {n-k}}} \over {N \choose n}}$

Where:

$N$ is the population size
$K$ is the number of success states in the population
$n$ is the number of draws
$k$ is the number of successes
$\textstyle {a \choose b}$ is a binomial coefficient

The pmf is positive when $\max(0,n+K-N)\leq k\leq \min(K,n).$

Combinatorial identities

As one would expect, the probabilities sum up to 1 :

$\sum _{{0\leq k\leq K}}{{K \choose k}{N-K \choose n-k} \over {N \choose n}}=1$

This is essentially Vandermonde's identity from combinatorics.

Also note the following identity holds:

${{{K \choose k}{{N-K} \choose {n-k}}} \over {N \choose n}}={{{n \choose k}{{N-n} \choose {K-k}}} \over {N \choose K}}.$

This follows from the symmetry of the problem, but it can also be shown by expressing the binomial coefficients in terms of factorials and rearranging the latter.

Application and example

The classical application of the hypergeometric distribution is sampling without replacement. Think of an urn with two types of marbles, black ones and white ones. Define drawing a white marble as a success and drawing a black marble as a failure (analogous to the binomial distribution). If the variable N describes the number of all marbles in the urn (see contingency table below) and K describes the number of white marbles, then N − K corresponds to the number of black marbles. In this example, X is the random variable whose outcome is k, the number of white marbles actually drawn in the experiment. This situation is illustrated by the following contingency table:

	drawn	not drawn	total
white marbles	k	K − k	K
black marbles	n − k	N + k − n − K	N − K
total	n	N − n	N

Now, assume (for example) that there are 5 white and 45 black marbles in the urn. Standing next to the urn, you close your eyes and draw 10 marbles without replacement. What is the probability that exactly 4 of the 10 are white? Note that although we are looking at success/failure, the data are not accurately modeled by the binomial distribution, because the probability of success on each trial is not the same, as the size of the remaining population changes as we remove each marble.

This problem is summarized by the following contingency table:

	drawn	not drawn	total
white marbles	k = 4	K − k = 1	K = 5
black marbles	n − k = 6	N + k − n − K = 39	N − K = 45
total	n = 10	N − n = 40	N = 50

The probability of drawing exactly k white marbles can be calculated by the formula

$P(X=k)=f(k;N,K,n)={{{K \choose k}{{N-K} \choose {n-k}}} \over {N \choose n}}.$

Hence, in this example calculate

$P(X=4)=f(4;50,5,10)={{{5 \choose 4}{{45} \choose {6}}} \over {50 \choose 10}}={5\cdot 8145060 \over 10272278170}=0.003964583\dots .$

Intuitively we would expect it to be even more unlikely for all 5 marbles to be white.

$P(X=5)=f(5;50,5,10)={{{5 \choose 5}{{45} \choose {5}}} \over {50 \choose 10}}={1\cdot 1221759 \over 10272278170}=0.0001189375\dots ,$

As expected, the probability of drawing 5 white marbles is roughly 35 times less likely than that of drawing 4.

Application to Texas Hold'em Poker

In Hold'em Poker players make the best hand they can combining the two cards in their hand with the 5 cards (community cards) eventually turned up on the table. The deck has 52 and there are 13 of each suit. For this example assume a player has 2 clubs in the hand and there are 3 cards showing on the table, 2 of which are also clubs. The player would like to know the probability of one of the next 2 cards to be shown being a club to complete his flush.

There are 4 clubs showing so there are 9 still unseen. There are 5 cards showing (2 in the hand and 3 on the table) so there are 52-5=47 still unseen.

The probability that one of the next two cards turned is a club can be calculated using hypergeometric with k=1, n=2, K=9 and N=47.

The probability that both of the next two cards turned are clubs can be calculated using hypergeometric with k=2, n=2, K=9 and N=47.

The probability that neither of the next two cards turned are clubs can be calculated using hypergeometric with k=0, n=2, K=9 and N=47.

Symmetries

Swapping the roles of black and white marbles:

$f(k;N,K,n)=f(n-k;N,N-K,n)$

Swapping the roles of drawn and not drawn marbles:

$f(k;N,K,n)=f(K-k;N,K,N-n)$

Swapping the roles of white and drawn marbles:

$f(k;N,K,n)=f(k;N,n,K)$

Relationship to Fisher's exact test

The test (see above) based on the hypergeometric distribution (hypergeometric test) is identical to the corresponding one-tailed version of Fisher's exact test^[2] ). Reciprocally, the p-value of a two-sided Fisher's exact test can be calculated as the sum of two appropriate hypergeometric tests (for more information see^[3] ).

Order of draws

The probability of drawing any sequence of white and black marbles (the hypergeometric distribution) depends only on the number of white and black marbles, not on the order in which they appear; i.e., it is an exchangeable distribution. As a result, the probability of drawing a white marble in the $i^{{{\text{th}}}}$ draw is^{[citation needed]}

$P(W_{i})={{\frac {K}{N}}}.$

Related distributions

Let X ~ Hypergeometric( $K$ , $N$ , $n$ ) and $p=K/N$ .

If $n=1$ then $X$ has a Bernoulli distribution with parameter $p$ .

Let $Y$ have a binomial distribution with parameters $n$ and $p$ ; this models the number of successes in the analogous sampling problem with replacement. If $N$ and $K$ are large compared to $n$ and $p$ is not close to 0 or 1, then $X$ and $Y$ have similar distributions, i.e., $P(X\leq k)\approx P(Y\leq k)$ .

If $n$ is large, $N$ and $K$ are large compared to $n$ and $p$ is not close to 0 or 1, then

$P(X\leq k)\approx \Phi \left({\frac {k-np}{{\sqrt {np(1-p)}}}}\right)$

where $\Phi$ is the standard normal distribution function

If the probabilities to draw a white or black marble are not equal (e.g. because white marbles are bigger/easier to grasp than black marbles) then $X$ has a noncentral hypergeometric distribution

Multivariate hypergeometric distribution

Multivariate Hypergeometric Distribution
Parameters	$c\in {\mathbb {N}}=\lbrace 0,1,\ldots \rbrace$ $(K_{1},\ldots ,K_{c})\in {\mathbb {N}}^{c}$ $N=\sum _{{i=1}}^{c}K_{i}$ $n\in \lbrace 0,\ldots ,N\rbrace$
Support	$\left\{{\mathbf {k}}\in {\mathbb {Z}}_{{0+}}^{c}\,:\,\forall i\ k_{i}\leq K_{i},\sum _{{i=1}}^{{c}}k_{i}=n\right\}$
pmf	${\frac {\prod _{{i=1}}^{{c}}{\binom {K_{i}}{k_{i}}}}{{\binom {N}{n}}}}$
Mean	$E(X_{i})={\frac {nK_{i}}{N}}$
Variance	${\text{Var}}(X_{i})={\frac {K_{i}}{N}}\left(1-{\frac {K_{i}}{N}}\right)n{\frac {N-n}{N-1}}$ ${\text{Cov}}(X_{i},X_{j})=-{\frac {nK_{i}K_{j}}{N^{2}}}{\frac {N-n}{N-1}}$

The model of an urn with black and white marbles can be extended to the case where there are more than two colors of marbles. If there are K_i marbles of color i in the urn and you take n marbles at random without replacement, then the number of marbles of each color in the sample (k₁,k₂,...,k_c) has the multivariate hypergeometric distribution. This has the same relationship to the multinomial distribution that the hypergeometric distribution has to the binomial distribution—the multinomial distribution is the "with-replacement" distribution and the multivariate hypergeometric is the "without-replacement" distribution.

The properties of this distribution are given in the adjacent table, where c is the number of different colors and $N=\sum _{{i=1}}^{{c}}K_{i}$ is the total number of marbles.

Example

Suppose there are 5 black, 10 white, and 15 red marbles in an urn. You reach in and randomly select six marbles without replacement. What is the probability that you pick exactly two of each color?

$P(2{\text{ black}},2{\text{ white}},2{\text{ red}})={{{5 \choose 2}{10 \choose 2}{15 \choose 2}} \over {30 \choose 6}}=.079575596816976$

Note: When picking the six marbles without replacement, the expected number of black marbles is 6×(5/30) = 1, the expected number of white marbles is 6×(10/30) = 2, and the expected number of red marbles is 6×(15/30) = 3.

Notes

↑ Rice, John A. (2007). Mathematical Statistics and Data Analysis (Third ed.). Duxbury Press. p. 42.
↑ Rivals, I.; Personnaz, L.; Taing, L.; Potier, M.-C (2007). "Enrichment or depletion of a GO category within a class of genes: which test?". Bioinformatics 23 (4): 401–407. doi:10.1093/bioinformatics/btl633. PMID 17182697.
↑ K. Preacher and N. Briggs. "Calculation for Fisher's Exact Test: An interactive calculation tool for Fisher's exact probability test for 2 x 2 tables (interactive page)".

References

Berkopec, Aleš (2007). "HyperQuick algorithm for discrete hypergeometric distribution". Journal of Discrete Algorithms 5 (2): 341. doi:10.1016/j.jda.2006.01.001.

Skala, M. (2011). "Hypergeometric tail inequalities: ending the insanity". unpublished note

External links

The Hypergeometric Distribution and Binomial Approximation to a Hypergeometric Random Variable by Chris Boucher, Wolfram Demonstrations Project.
Weisstein, Eric W., "Hypergeometric Distribution", MathWorld.

Probability distributions

Discrete univariate with finite support

Benford Bernoulli Beta-binomial binomial categorical hypergeometric Poisson binomial Rademacher discrete uniform Zipf Zipf–Mandelbrot

Discrete univariate with infinite support

beta negative binomial Borel Conway–Maxwell–Poisson discrete phase-type Delaporte extended negative binomial Gauss–Kuzmin geometric logarithmic negative binomial parabolic fractal Poisson Skellam Yule–Simon zeta

Continuous univariate supported on a bounded interval, e.g. [0,1]

Arcsine ARGUS Balding–Nichols Bates Beta Beta rectangular Irwin–Hall Kumaraswamy logit-normal Noncentral beta raised cosine Triangular U-quadratic uniform Wigner semicircle Xenakis

[[List of probability distributions#Supported_on_semi-infinite_intervals.2C_usually_.5B0.2C.E2.88.9E.29|Continuous univariate supported on a semi-infinite interval, usually [0,∞)]]

Benini
Benktander 1st kind
Benktander 2nd kind
Beta prime
Burr
chi-squared
chi
Coxian
Dagum
Davis
EL
Erlang
exponential
F
folded normal
Flory-Schulz
Fréchet
Gamma
Gamma/Gompertz
generalized inverse Gaussian
Gompertz
half-logistic
half-normal
Hotelling's T-squared
hyper-Erlang
hyperexponential
hypoexponential
inverse chi-squared (scaled inverse chi-squared)
inverse Gaussian
inverse gamma
Kolmogorov
Lévy
log-Cauchy
log-Laplace
log-logistic
log-normal
Maxwell–Boltzmann
Maxwell–Jüttner
Mittag–Leffler
Nakagami
noncentral chi-squared
Pareto
phase-type
Poly-Weibull
Rayleigh
relativistic Breit–Wigner
Rice
Rosin–Rammler
shifted Gompertz
truncated normal
type-2 Gumbel
Weibull
Wilks' lambda

Continuous univariate supported on the whole real line (−∞, ∞)

Cauchy exponential power Fisher's z generalized normal generalized hyperbolic geometric stable Gumbel Holtsmark hyperbolic secant Johnson SU Landau Laplace Linnik logistic noncentral t normal (Gaussian) normal-inverse Gaussian skew normal slash stable Student's t type-1 Gumbel variance-gamma Voigt

Continuous univariate with support whose type varies

generalized extreme value generalized Pareto Tukey lambda q-Gaussian q-exponential shifted log-logistic

Mixed continuous-discrete univariate distributions

rectified Gaussian

Multivariate (joint)

Discrete Ewens multinomial Dirichlet-multinomial negative multinomial Continuous Dirichlet Generalized Dirichlet multivariate normal Multivariate stable multivariate Student normal-scaled inverse gamma normal-gamma Matrix-valued inverse matrix gamma inverse-Wishart matrix normal matrix t matrix gamma normal-inverse-Wishart normal-Wishart Wishart

Directional

Univariate (circular) directional Circular uniform univariate von Mises wrapped normal wrapped Cauchy wrapped exponential wrapped Lévy Bivariate (spherical) Kent Bivariate (toroidal) bivariate von Mises Multivariate von Mises–Fisher Bingham

Degenerate and singular

Degenerate discrete degenerate Dirac delta function Singular Cantor

Families

Circular compound Poisson elliptical exponential natural exponential location-scale maximum entropy mixture Pearson Tweedie wrapped

v t e Some common univariate probability distributions

Continuous	beta Cauchy chi-squared exponential F gamma Laplace log-normal normal Pareto Student's t uniform Weibull

Discrete	Bernoulli binomial discrete uniform geometric hypergeometric negative binomial Poisson

List of probability distributions

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.