Derivation for hypergeometric distribution formula and comparsion with Bernoulli formula

Question

To understand the binomial probability distribution function, I was lucky to see the connection between the Bernoulli probability: $P(X=k) = {n\choose k}p^k(1-p)^{1-k}$, which is based on the formula for one try: $P(x=k) = p^k(1-p)^{1-k}$ which is $p$ for $k=1$ and $1-p$ for $k=0$. The Bernoulli probability distribution function is a function that represents the probability of having k successes on $n$ trials of something.

If we do the experiment more than one time, let's say, $k$ times and the probability stays the same on every trial, then the probability function $P(s)$ is just the number of $s$ successes in these $k$ trials. This is exactly $kCs$ or $k\choose s$. Why? See the text at $(1)$in the end.

Now, for the hypergeometric distribution, we're doing kinda like in the Bernoulli case, but the probability changes after very trial. We can think of the success and failure as being the removal of a ball of color $A$ from a sack of balls of color $A$ or $B$. In the Bernoulli case, it's like we putting the ball back in the sack for the next trial, so the probability of getting a ball of color $A$ is the same on every trial. In the hypergeometric case is like we were not putting it back again, so the probability of getting a ball of color $A$ changes after each trial. For some reason, its formula is: $$P(X=k) = \frac{{K\choose k} {{N-K}\choose {n-k}}}{N\choose n}$$

Main question: How to find the formula for the hypergeometric distribution?

** (1) Explanation for the Bernoulli formula (the combinatoric part):**

Our experiment for let's say, $k=5$ trials when $S$ means success and $F$ means failure looks like this:

$$SSSSS\\ SSSSF \\ SSSFS \\ SSFSS \\ \cdots \\ FFFFF$$

Our function $P(s=3)$ should count how many objects exists in the set above with exactly 3 $S$ letters, for example: $SSSFF, SFSFS, SSFFS, \cdots$. To count this, we're gonna think about how many permutations of $A,B,C$ exist in $A,B,C,D,E$, that is, how many ways can we do things like:

$$ABCDE\\ABDCE\\ADEBC\\ \cdots \\ EDBCA$$

We know that there are $5!$ ways to permute every symbol, but we just care about the permutations on $A,B,C$, so $ABCDE$ and $ABCED$ are the same for this case. In general, for every permutation in the set above, there will be an equivalent one with $D$ and $E$ switched. Other example can be: $ABDEC$ being the same as $ABEDC$, so we're gonna divide by how many ways there are to permute $E$ and $D$, which is $2!$. So the number of ways to permute $A,B,C$ in $A,B,C,D,E$ is $\frac{5!}{2!} = \frac{5!}{(5-3)!}$. This is the known formula $\frac{p!}{(p-k)!}$.

Getting back to our case, I see the problem of counting how many $3$ $S$ucesses in $5$ trials as counting how many permutations of letters $A,B,C$ in the set $A,B,C,D,E$, with the restriction that we don't want to count repetitions (you'll understand this part soon). For example, the $3$ sucesses would look like this:

$$SSSFF\\SSFSF\\SFSFS\\\cdots\\FFSSS$$ I don't know exactly how to explain this part, but I see this as being the same as counting the permutations $A,B,C$ inside $A,B,C,D,E$, except that now, $ABCDE = ACBDE = BACDE = BCADE = CABDE = CBADE$, that is, $S_1S_2S_3FF = S_2S_1S_3FF = S_3S_1S_2FF = S_1S_3S_2FF = S_2S_3S_1FF = S_3S_2S_1FF$. I could differentiate the $F$ letters by $F_1, F_2$ but since we're not gonna count repetitions on $F$ as in the formula $\frac{p!}{(p-k)!}$, I'm considering that there exists only one case. Now we must just se that in general there will be $3!$ equal cases for each object, because $ABCDE = ACBDE = \cdots$. The reason is obvious: there is $3!$ ways to permute $A,B,C$ or $S_1,S_2,S_3$, so we just divide the formula by $3!$ or $k!$, that's why the formula for combination is ${p\choose k} = \frac{p!}{k!(p-k)!}$

UPDATE:

While writing this, I realized that it's a lot simpler if we just consider the permutations of the following letters: $S_1,S_2,S_3,F_1,F_2$, eliminate the permutations for $F_1,F_2$ by dividing by $2!$ and eliminate the permutations of $S_1S_2S_3$ because $S_1S_2S_3F_1F_2 = S_1S_3S_2F_1F_2 = \cdots $, which is $3!$ in total. I made a mess but I think it's good to see my thinking process.

Now that we counted how many successes there are, it's just a matter of multiplying by $p^k(1-p)^{1-k}$ to get the formula.

Answer 1

If there are $N$ balls total, of which $K$ are "red," and $N-K$ are "white," and $n$ balls are randomly selected without replacement, then the probability that exactly $k$ of the $n$ balls are red is given by $$\Pr[X = k] = \frac{\binom{K}{k}\binom{N-k}{n-k}}{\binom{N}{n}}.$$ To see where this formula comes from, label the balls $$R_1, R_2, \ldots, R_K, W_{K+1}, W_{K+2}, \ldots, W_N.$$ Note that the way we have labeled the balls allows us to uniquely identify them simply by the subscript, since there are no repeated subscripts. Now, our sample space $\frak S$ consists of all $n$-subsets of $S = \{R_1, R_2, \ldots, R_K, W_{K+1}, W_{K+2}, \ldots, W_N\}$: $${\frak S} = \{s \subseteq S : |s| = n\}.$$ What is the size of this sample space; i.e., how many $n$-subsets are there of $S$, or how many ways are there to choose $n$ distinct balls from a group of $N$ numbered balls? Obviously, this is just $$|{\frak S}| = \binom{N}{n} = \frac{N!}{n! (N-n)!}.$$ This is where the denominator comes from. All that is left now is to enumerate those $n$-subsets in which exactly $k$ of the balls are red. To do this, we note that any such subset would not only have exactly $k$ red balls, but also exactly $n-k$ white balls, since the number of red balls drawn ($k$), plus the number of white balls drawn ($n-k$), must equal the total number of balls drawn ($n$). How many ways are there to choose $k$ red balls from $S$ and $n-k$ white balls from $S$? This is also obvious if we look at the structure of $S$; there are $$\binom{K}{k}$$ ways to choose $k$ red balls from the set $\{R_1, R_2, \ldots, R_K\}$ of red balls, and $$\binom{N-K}{n-k}$$ ways to choose $n-k$ white balls from the set $\{W_{K+1}, W_{K+2}, \ldots, W_N\}$. Moreover, the choices of which numbered red and white balls are selected are independent of each other; thus the total number of desired outcomes is simply the product of each individual event, so the total number of ways to have exactly $k$ red balls from $n$ selected balls is $$\binom{K}{k}\binom{N-k}{n-k},$$ the numerator of our probability.

If this level of abstraction is difficult to grasp, it helps to consider a numeric example. Suppose we have $N = 9$ balls, $K = 4$ of which are red (so $N - K = 9 - 4 = 5$ are white). And suppose we are interested in the probability that, among $n = 3$ balls chosen at random, we obtain exactly $k = 1$ red ball (and implicitly, $n - k = 3-1 = 2$ white balls). Obviously, there are simply $\binom{N}{n} = \binom{9}{3} = 84$ ways to select any three balls out of nine without replacement. How many of these outcomes have exactly $1$ red ball? There were only $4$ red balls to choose from, so there are just $\binom{K}{k} = \binom{4}{1} = 4$ ways to get one red ball. But we also have to account for the number of ways to select white balls; this is $\binom{N-k}{n-k} = \binom{5}{2} = 10$; thus there are $4(10) = 40$ such outcomes with exactly $1$ red and $2$ white balls, and the resulting probability is $$\Pr[X = 1] = \frac{40}{84} = \frac{10}{21}.$$

Specifically, we can enumerate the desired outcomes as follows:

$$\{R_1 , W_5 , W_6 \}, \{ R_1 , W_5 , W_7 \}, \{ R_1 , W_5 , W_8 \}, \{ R_1 , W_5 , W_9 \}, \{ R_1 , W_6 , W_7 \}, \{ R_1 , W_6 , W_8 \}, \{ R_1 , W_6 , W_9 \}, \{ R_1 , W_7 , W_8 \}, \{ R_1 , W_7 , W_9 \}, \{ R_1 , W_8 , W_9 \}, \{ R_2 , W_5 , W_6 \}, \{ R_2 , W_5 , W_7 \}, \{ R_2 , W_5 , W_8 \}, \{ R_2 , W_5 , W_9 \}, \{ R_2 , W_6 , W_7 \}, \{ R_2 , W_6 , W_8 \}, \{ R_2 , W_6 , W_9 \}, \{ R_2 , W_7 , W_8 \}, \{ R_2 , W_7 , W_9 \}, \{ R_2 , W_8 , W_9 \}, \{ R_3 , W_5 , W_6 \}, \{ R_3 , W_5 , W_7 \}, \{ R_3 , W_5 , W_8 \}, \{ R_3 , W_5 , W_9 \}, \{ R_3 , W_6 , W_7 \}, \{ R_3 , W_6 , W_8 \}, \{ R_3 , W_6 , W_9 \}, \{ R_3 , W_7 , W_8 \}, \{ R_3 , W_7 , W_9 \}, \{ R_3 , W_8 , W_9 \}, \{ R_4 , W_5 , W_6 \}, \{ R_4 , W_5 , W_7 \}, \{ R_4 , W_5 , W_8 \}, \{ R_4 , W_5 , W_9 \}, \{ R_4 , W_6 , W_7 \}, \{ R_4 , W_6 , W_8 \}, \{ R_4 , W_6 , W_9 \}, \{ R_4 , W_7 , W_8 \}, \{ R_4 , W_7 , W_9 \}, \{ R_4 , W_8 , W_9 \} $$

Answer 2

It helps to think in terms of the number of subsets of $[N]=\{1,\dots,N\}$ with various properties.

Imagine the "success" outcomes form the set $[K]$ which is a subset of $[N]$.

The numerator in the hypergeometric distribution formula gives the number of subsets of $[N]$ of size $n$ having exactly $k$ elements from $[K]$.

The denominator gives the total number of subsets of $[N]$ of size $n$.

Since the subsets are all equally likely (an important point), the ratio is the probability you want.

Answer 3

Here's another way:

There are $N$ balls, $K$ are red and $N-K$ are white. We take a sample of $n$ balls without replacement. What is the probability that we have exactly $k$ red balls in our sample?

All of the ways in which we can choose our sample so that it contains $k$ red balls occur with the same probability. For example $$ P(\underbrace{red,\ldots,red}_{k},\underbrace{white,\ldots,white}_{n-k}) = P(red,white,\underbrace{red,\ldots,red}_{k-1},\underbrace{white,\ldots,white}_{n-k-1}). $$ How many different such ways are there? This is just the binomial coefficient, ${n \choose k}.$

So \begin{align*} &P(k \text{ red balls in a sample of } n) \\ &= {n \choose k}P(\underbrace{red,\ldots,red}_{k},\underbrace{white,\ldots,white}_{n-k})\\ &= {n \choose k} \underbrace{\frac{K}{N}\frac{K-1}{N-1}\cdots\frac{K-(k-1)}{N-(k-1)}}_{k \text{ terms}} \,\,\, \underbrace{\frac{N-K}{N-k}\cdots\frac{N-(n-k-1)}{N-(n-1)}}_{n-k \text{ terms}}\\ &= {n \choose k} \frac{\frac{K!}{(K-k)!}\frac{(N-K)!}{(N-K-(n-k))!}}{\frac{N!}{(N-n)!}}\\ &= \frac{n!}{k!(n-k)!} \frac{\frac{K!}{(K-k)!}\frac{(N-K)!}{(N-K-(n-k))!}}{\frac{N!}{(N-n)!}}\\ &= \frac{{K \choose k} {N-K \choose n-k}}{{N \choose n}}. \end{align*}