{
  "id": "enwiki-001364778061",
  "slug": "hypergeometric-distribution",
  "title": "Hypergeometric distribution",
  "qid": "",
  "lead": "{{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.…",
  "body": "{{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&nbsp;−&nbsp;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 ==Occurrence and applications== ===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&nbsp;=&nbsp;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.",
  "categories": [
    "23241497",
    "23603337",
    "24506888",
    "24745114",
    "26220375",
    "27424624"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1364778061",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1784374968.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001364778061",
    "type": "webpage",
    "title": "Hypergeometric distribution",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/hypergeometric-distribution",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001364778061",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1364778061",
    "note": "Immutable snapshot enwiki-001364778061"
  }
}