Hypergeometric distribution

{{Infobox probability distribution | name = Hypergeometric | type = mass | pdf_image = | cdf_image = | notation = \mathrm{Hypergeometric}(N,K,n) | parameters = \begin{align}N&\in \left\{0,1,2,\dots\right\} \\ K&\in…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 15 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

{{Infobox probability distribution | name = Hypergeometric | type = mass | pdf_image = | cdf_image = | notation = \mathrm{Hypergeometric}(N,K,n) | parameters = \begin{align}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{align}\, | support = \scriptstyle{k\, \in\, \{\max{(0,\, n+K-N)},\, \dots,\, \min{(n,\, K)}\}}\, | pdf = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}} | cdf = 1-{{{n \choose {k+1}}{{N-n} \choose {K-k-1}}}\over {N \choose K}} \,_3F_2\!\!\left[\begin{array}{c}1,\ k+1-K,\ k+1-n \\ k+2,\ N+k+2-K-n\end{array};1\right], where \,_pF_q is the generalized hypergeometric function | mean = n {K \over N} | median = \left \lfloor n {K \over N} \right \rfloor or \left \lceil n {K \over N} \right \rceil | mode = \left \lceil \frac{(n+1)(K+1)}{N+2} \right \rceil-1, \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)} | kurtosis = \left.\frac{1}{n K(N-K)(N-n)(N-2)(N-3)}\cdot\right.…

{{Infobox probability distribution | name = Hypergeometric | type = mass | pdf_image = | cdf_image = | notation = \mathrm{Hypergeometric}(N,K,n) | parameters = \begin{align}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{align}\, | support = \scriptstyle{k\, \in\, \{\max{(0,\, n+K-N)},\, \dots,\, \min{(n,\, K)}\}}\, | pdf = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}} | cdf = 1-{{{n \choose {k+1}}{{N-n} \choose {K-k-1}}}\over {N \choose K}} \,_3F_2\!\!\left[\begin{array}{c}1,\ k+1-K,\ k+1-n \\ k+2,\ N+k+2-K-n\end{array};1\right], where \,_pF_q is the generalized hypergeometric function | mean = n {K \over N} | median = \left \lfloor n {K \over N} \right \rfloor or \left \lceil n {K \over N} \right \rceil | mode = \left \lceil \frac{(n+1)(K+1)}{N+2} \right \rceil-1, \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)} | kurtosis = \left.\frac{1}{n K(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) {}+6 n K (N-K)(N-n)(5N-6)\big] | entropy = | mgf = \frac{\binom{N-K}{n} \,_2F_1(-n, -K\,;\, N - K - n + 1\,;\, e^{t})}{\binom{N}{n}} | char = \frac{\binom{N-K}{n} \,_2F_1(-n, -K\,;\, N - K - n + 1\,;\, e^{it})} {\binom{N}{n}} }} In probability theory and statistics, the hypergeometric distribution is a discrete probability distribution that describes the probability of k successes (random draws for which the object drawn has a specified feature) in n draws, without replacement, from a finite population of size N that contains exactly K objects with that feature, where in each draw is either a success or a failure. In contrast, the binomial distribution describes the probability of k successes in n draws with replacement. p_X(k) = \Pr(X = k) = \frac{\binom{K}{k} \binom{N - K}{n-k}}{\binom{N}{n}}, where N is the population size, K is the number of success states in the population, n is the number of draws (i.e. quantity drawn in each trial), k is the number of observed successes, \textstyle {a \choose b} is a binomial coefficient.

The is positive when \max(0, n+K-N) \leq k \leq \min(K,n) . A random variable distributed hypergeometrically with parameters N , K and n is written X \sim \operatorname{Hypergeometric}(N,K,n) and has probability mass function p_X(k) above.

Combinatorial identities

As required, we have \sum_{0\leq k\leq \textrm{min}(n,K)} { {K \choose k} { N-K \choose n-k} \over {N \choose n} }

Working example

The classical application of the hypergeometric distribution is sampling without replacement. Think of an urn with two colors of marbles, red and green. Define drawing a green marble as a success and drawing a red marble as a failure.

Let N describe the number of all marbles in the urn (see contingency table below) and K describe the number of green marbles, then N − K corresponds to the number of red marbles. Now, standing next to the urn, you close your eyes and draw n marbles without replacement. Define X as a random variable whose outcome is k, the number of green marbles drawn in the experiment.

This situation is illustrated by the following contingency table: Indeed, we are interested in calculating the probability of drawing k green marbles in n draws, given that there are K green marbles out of a total of N marbles. For this example, assume that there are 5 green and 45 red 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 green?

This problem is summarized by the following contingency table: To find the probability of drawing k green marbles in exactly n draws out of N total draws, we identify X as a hyper-geometric random variable to use the formula P(X=k) = f(k;N,K,n) = {{{K \choose k} {{N-K} \choose {n-k}}}\over {N \choose n}}. To intuitively explain the given formula, consider the two symmetric problems represented by the identity {{K \choose k} {N-K \choose n-k}\over {N \choose n}} = {{{n \choose k} {{N-n} \choose {K-k}}} \over {N \choose K}} left-hand side - drawing a total of only n marbles out of the urn.

We want to find the probability of the outcome of drawing k green marbles out of K total green marbles, and drawing n-k red marbles out of N-K red marbles, in these n rounds. right hand side - alternatively, drawing all N marbles out of the urn. We want to find the probability of the outcome of drawing k green marbles in n draws out of the total N draws, and K-k green marbles in the rest N-n draws.

Back to the calculations, we use the formula above to calculate the probability of drawing exactly k green marbles 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 that all 5 green marbles will be among the 10 drawn.

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 green marbles is roughly 35 times less likely than that of drawing 4. 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 green and drawn marbles: f(k;N,K,n) = f(k;N,n,K) These symmetries generate the dihedral group D_4 . P(G_i) = \frac{K}{N}.

This is an ex ante probability—that is, it is based on not knowing the results of the previous draws.

Tail bounds

Let X \sim \operatorname{Hypergeometric}(N,K,n) and p=K/N . Then for 0 we can derive the following bounds: \begin{align} \Pr[X\le (p - t)n] &\le e^{-n\text{D}(p-t\parallel p)} \le e^{-2t^2n}\\ \Pr[X\ge (p+t)n] &\le e^{-n\text{D}(p+t\parallel p)} \le e^{-2t^2n}\\ \end{align}\! where D(a\parallel b)=a\log\frac{a}{b}+(1-a)\log\frac{1-a}{1-b} is the Kullback–Leibler divergence and it is used that D(a\parallel b) \ge 2(a-b)^2 . Note: In order to derive the previous bounds, one has to start by observing that X = \frac{\sum_{i=1}^n Y_i}{n} where Y_i are dependent random variables with a specific distribution D . Because most of the theorems about bounds in sum of random variables are concerned with independent sequences of them, one has to first create a sequence Z_i of independent random variables with the same distribution D and apply the theorems on X' = \frac{\sum_{i=1}^{n}Z_i}{n} .

Then, it is proved from Hoeffding that the results and bounds obtained via this process hold for X as well. If n is larger than N/2, it can be useful to apply symmetry to "invert" the bounds, which give you the following: \begin{align} \Pr[X\le (p - t)n] &\le e^{-(N-n)\text{D}(p+\tfrac{tn}{N-n}||p)} \le e^{-2 t^2 n \tfrac{n}{N-n}}\\ \\ \Pr[X\ge (p+t)n] &\le e^{-(N-n)\text{D}(p-\tfrac{tn}{N-n}||p)} \le e^{-2 t^2 n \tfrac{n}{N-n}}\\ \end{align}\!

Let X\sim\operatorname{Hypergeometric}(N,K,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 \le k) \approx P(Y \le 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 \le k) \approx \Phi \left( \frac{k-n p}{\sqrt{n p (1-p)}} \right) where \Phi is the standard normal distribution function If the probabilities of drawing a green or red marble are not equal (e.g. because green marbles are bigger/easier to grasp than red marbles) then X has a noncentral hypergeometric distribution The beta-binomial distribution is a conjugate prior for the hypergeometric distribution.

The following table describes four distributions related to the number of successes in a sequence of draws: | name = Multivariate hypergeometric distribution | type = mass | pdf_image = | cdf_image = | parameters = c \in \mathbb{N}_{+} = \lbrace 1, 2, \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 \left(\mathbb{Z}_{0+}\right)^c \, : \, \forall i\ k_i \le K_i , \sum_{i=1}^{c} k_i = n \right\} | pdf = \frac{\prod\limits_{i=1}^c \binom{K_i}{k_i}}{\binom{N}{n}} | cdf = | mean = \operatorname E(k_i) = n\frac{K_i}{N} | median = | mode = | variance = \operatorname{Var}(k_i) = n \frac{N-n}{N-1} \;\frac{K_i}{N} \left(1-\frac{K_i}{N}\right) \operatorname{Cov}(k_i,k_j) = -n \frac{N-n}{N-1} \;\frac{K_i}{N} \frac{K_j}{N}, i\ne j \operatorname{Corr}(k_i,k_j) = -\sqrt{\frac{K_i K_j}{\left(N-K_i\right)\left(N-K_j\right)}} | skewness = | kurtosis = | entropy = | mgf = | char = }} The model of an urn with green and red 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 1 , k 2 ,..., k c ) has the multivariate hypergeometric distribution: \Pr(X_1 = k_1, \ldots, X_c = k_c) = \frac{\prod\limits_{i=1}^c \binom{K_i}{k_i}}{\binom{N}{n}} 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 in the urn. P(2\text{ black}, 2\text{ white}, 2\text{ red}) = {{{5 \choose 2}{10 \choose 2} {15 \choose 2}}\over {30 \choose 6}} = 0.079575596816976

Application to auditing elections

Election audits typically test a sample of machine-counted precincts to see if recounts by hand or machine match the original counts. Mismatches result in either a report or a larger recount.

The sampling rates are usually defined by law, not statistical design, so for a legally defined sample size , what is the probability of missing a problem which is present in precincts, such as a hack or bug? This is the probability that Bugs are often obscure, and a hacker can minimize detection by affecting only a few precincts, which will still affect close elections, so a plausible scenario is for to be on the order of 5% of .

Audits typically cover 1% to 10% of precincts (often 3%), so they have a high chance of missing a problem. For example, if a problem is present in 5 of 100 precincts, a 3% sample has 86% probability that so the problem would not be noticed, and only 14% probability of the problem appearing in the sample (positive ): \begin{align} \operatorname{\boldsymbol\mathcal P}\{\ X = 0\ \} & = \frac{\ \left[\ \binom{\text{Hack}}{0} \binom{ N\ -\ \text{Hack}}{ n\ -\ 0 }\ \right]\ }{\left[\ \binom{N}{n}\ \right]} = \frac{\ \left[\ \binom{N\ -\ \text{Hack}}{n}\ \right]}{\ \left[\ \binom{N}{n}\ \right]\ } = \frac{\ \left[\ \frac{\ (N\ -\ \text{Hack})!\ }{n!(N\ -\ \text{Hack}-n)!}\ \right]\ }{\left[\ \frac{N!}{n!(N\ -\ n)!}\ \right]} = \frac{\ \left[\ \frac{(N-\text{Hack})!}{(N\ -\ \text{Hack}\ -\ n)!}\ \right]\ }{\left[\ \frac{N!}{(N\ -\ n)!}\ \right]} \\[8pt] & = \frac{\ \left[\ \binom{100-5}{3}\ \right]\ }{\ \left[\ \binom{100}{3}\ \right]\ } = \frac{\ \left[\ \frac{(100-5)!}{(100-5-3)!}\ \right]\ }{\left[\ \frac{100!}{(100-3)!}\ \right]} = \frac{\ \left[\ \frac{95!}{92!}\ \right]\ }{\ \left[\ \frac{100!}{97!}\ \right]\ } = \frac{\ 95\times94\times93\ }{100\times99\times98} = 86\% \end{align} The sample would need 45 precincts in order to have probability under 5% that k = 0 in the sample, and thus have probability over 95% of finding the problem: \operatorname{\boldsymbol\mathcal P}\{\ X = 0\ \} = \frac{\ \left[\ \binom{100-5}{45}\ \right]\ }{\left[\ \binom{100}{45}\ \right]} = \frac{\ \left[\ \frac{95!}{50!}\ \right]\ }{\left[\ \frac{100!}{55!}\ \right]} = \frac{\ 95\times 94\times \cdots \times 51\ }{\ 100\times 99\times \cdots \times 56\ } = \frac{\ 55\times 54\times 53\times 52\times 51\ }{\ 100\times 99\times 98\times 97\times 96\ } = 4.6\% ~.

There are 4 clubs showing so there are 9 clubs 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 exactly 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 .

(about 31.64%) 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 . (about 3.33%) 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 .

(about 65.03%) P(X=4) = f(4;80,6,20) = {{{6 \choose 4} {{80-6} \choose {20-4}}}\over {80 \choose 20}} \approx 0.02853791 Similarly, the chance for hitting 5 spots out of 6 selected is {{{6 \choose 5} {{74} \choose {15}}} \over {80 \choose 20}} \approx 0.003095639 while a typical payout might be $88. The payout for hitting all 6 would be around $1500 (probability ≈ 0.000128985 or 7752-to-1).

The only other nonzero payout might be $1 for hitting 3 numbers (i.e., you get your bet back), which has a probability near 0.129819548. Taking the sum of products of payouts times corresponding probabilities we get an expected return of 0.70986492 or roughly 71% for a 6-spot, for a house advantage of 29%. Other spots-played have a similar expected return.

This very poor return (for the player) is usually explained by the large overhead (floor space, equipment, personnel) required for the game.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1364778061 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

7 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.