The Negative Binomial Distribution (sampling with replacement)
Consider a sequence of Bernoulli trails with success rate $p$. The negative binomial distribution is a random variable $X$ that denotes the number of failures until $r$ successes. Now we have
$$ P(X = k) = \binom{k+r-1}{r-1} (1-p)^k p^r = \binom{k+r-1}{k} (1-p)^k p^r $$
To see why the formula above is true, suppose that there are exactly $k$ failures before the $r$-th success. Then there are a total of $k+r$ trials. The last trial has to be a success, so among the first $k+r-1$ trials there must be $r-1$ successes. Thus there are a total of $\binom{k+r-1}{r-1}$ locations the first $r-1$ successes can occur. For each of these situations, the probability is $(1-p)^k p^r$.
We can also easily compute the expectation of $X$. The expected number of trails to get $r$ successes is just $r/p$. Therefore, the expected number of failures is $$ \mathbb{E}[X] = r/p - r = r(1-p)/p. $$
The Hypergeometric Distribution (sampling without replacement)
The Probability Mass Function
Consider drawing (without replacement) $n$ balls from a container that contains $N$ balls, $K$ of which are red, and the remaining are black. Let $X$ denote the number of red balls that we draw. What is the distribution of $X$?
We can write out the pmf for $X$ in two different ways. Our goal is to compute $P(X=m)$.
-
Consider a random permutation of the $N$ balls in a straight line, and we pick the first $n$ . We count the number of ways that the $K$ can be distributed among all $N$ balls. Obviously there are $\binom{N}{K}$ possible positions, and each one of them is equally likely. Now we count the number of ways that the $K$ red balls can be distributed so that the first $n$ balls (the ones we pick) has exactly $m$ red balls. This is obviously equal to $\binom{n}{m} \cdot \binom{N-n}{K-m}$: first we choose $m$ locations to place the red balls among the first $n$ balls. Second we choose $K-m$ positions to place the remaining red balls among the remaining $N-n$ positions. Therefore finally we find that
$$ P(X=m) = \frac{\binom{n}{m}\cdot \binom{N-n}{K-m}}{\binom{N}{K}} $$
-
There is an alternative way to consider this problem. We also consider lining up all $N$ balls. We count the number of ways that the $n$ balls we pick can be placed among the $N$ balls. Clearly there are $\binom{N}{n}$ ways in total. Now we count how many ways we can pick $n$ balls so that there are exactly $m$ red balls in them. Notice that there exactly $K$ red balls positioned among the $N$ balls. We have to pick $m$ of them. Then, we need to pick $n-m$ white balls among the $N-K$ red balls. So the final pmf we get is
$$ P(X=m) = \frac{\binom{K}{m}\cdot \binom{N-K}{n-m}}{\binom{N}{n}} $$
It is easy to check that these two functions are in fact equal. Check Hypergeometric Random Variable for reference. Moreover, the expected value, intuitively, is
$$ \mathbb{E}[X] = \frac{nK}{N}. $$
Symmetry for Thought
The hypergeometric random variable actually has a lot of symmetries. To understand why, consider the following experiment:
- First we draw $K$ balls from $N$ balls (without replacement) and color them red. Then we put the balls back into the urn. Now $K$ out of $N$ balls are red, just as before.
- Second, using the same urn, we draw $n$ balls and color them green, and put the balls back.
Now let $X$ denote the number of balls with both colors. Note that after we first color $K$ balls red and then draw $n$ balls to color them green, the expected number of balls with both colors is exactly
$$ P(X=m) = \frac{\binom{n}{m}\cdot \binom{N-n}{K-m}}{\binom{N}{K}} $$
But the order in which we color the balls don't really matter. If we color the green balls first, then we get
$$ P(X=m) = \frac{\binom{K}{m}\cdot \binom{N-K}{n-m}}{\binom{N}{n}} $$
Therefore, we proved again, via this simple thought experiment, that $K$ and $n$ are symmetric for this function.