# Geometric distribution without replacement

On an attempt to solve this problem I've managed to reduce it to finding the expected number of white balls picked until one black ball is observed (let's call that value $v$). Except that, unlike the geometric distribution, this needs to be done without replacement. Hypergeometric distribution doesn't come to the rescue as the number of black balls picked is immaterial (and of course the white balls must be picked consecutively). So I am looking for a way to compute $v$, or at least its underlying distribution. I've tried to search online but couldn't find a distribution that readily fits this.

So the problem is:

Consider an urn having total of $n$ balls, $w$ of them are white, and the rest is black. Pick $j$ balls without replacement. What is the expected number of white balls that will be picked before a black ball is observed ? Notice that the total number of balls picked, $j$, is fixed.

My guess is that cumulative hypergeometric distribution could be used, while dividing somewhere by the number of ways the black balls intersperse the white ones (after the first black ball is observed). But I have little intuition how to go through with this. I.e. to divide before taking the cumulative distribution or after?

Update

Based on a question in the comments below, to be clear: the desired value is the expected number of white balls observed until either a black ball is observed, or $j$ picks happened, whichever comes earlier.

Thank you.

• This is not quite clear to me. If $j \le w$ then it is possible that no black ball is observed, while if $j \gt w$ then the particular value of $j$ is irrelevant to the calculation. Is your question asking for the expectation conditional on a black ball being observed? – Henry Apr 7 '12 at 11:48
• @Henry: No, the expectation is not conditional on a black ball being observed. So to be clear: the desired value is the expected number of white balls observed until either a black ball is observed, or $j$ picks happened, whichever comes earlier. – Mohammad Alaggan Apr 7 '12 at 11:51

I am going to interpret the question as follows: Find the expected number of white balls drawn before a black one is seen among $j$ draws without replacement, where if no black ball is seen, then the observation takes the value $j$. If this is not what you intend, please advise and I will revise accordingly.

We can use a nice, handy trick to find the expected value.

First, let's set out some notation. Let $X$ be the number of white balls seen before the first black ball is drawn in a sample of size $n$ taken without replacement from $n = w + b$ balls. Obviously $X \in \{0,1,\ldots,w\}$ with probability 1. Now, define $\newcommand{\Zj}{Z^{(j)}}\Zj$ to be the number of white balls seen before the first black ball from the first $j$ draws, or $j$ otherwise. Hence $\Zj = \min(X,j)$. We seek $\newcommand{\E}{\mathbb E}\renewcommand{\Pr}{\mathbb P}\E \Zj$. We need only consider $j \leq w$, since $\E \Zj = \E X$ for $j \geq w$.

Fact: If $Y$ is a nonnegative integer-valued random variable, then $$\E Y = \sum_{k=1}^\infty \Pr(Y \geq k) \>.$$

The proof is relatively easy and is omitted. It is a special case of the more general result that if $Y \geq 0$ almost surely, then $\E Y = \int_0^\infty \Pr(Y > y) \,\mathrm d y$.

Now, back to business. The key is to recognize the following equivalence of events, valid for $k \in \{0,\ldots,j\}$: $$\{ \Zj \geq k\} = \{ X \geq k\} \>.$$

Hence we have $$\E \Zj = \sum_{k=1}^j \Pr(\Zj \geq k) = \sum_{k=1}^j \Pr(X \geq k) = \sum_{k=1}^j \frac{{w \choose k}}{{n \choose k}} \>,$$ where the last equality follows from the fact that $X \geq k$ if and only if the first $k$ balls drawn are white.

Some binomial-coefficient manipulations yield $$\E \Zj = \sum_{k=1}^j \frac{{w \choose k}}{{n \choose k}} = \frac{w}{n-w+1}\left(1 - \frac{{{w-1} \choose j}}{{n \choose j}} \right) \>.$$

Post scriptum: In case the last equality looks at all mysterious, we can give a short sketch of the proof. Let $S_k = \Pr(X \geq k)$ and $p_k = \Pr(X = k) = S_k - S_{k+1}$. Then, $$\mu = \E\Zj = \sum_{k=1}^j S_k = \sum_{k=1}^{j-1} k p_k + j S_j \>.$$ Now, note that $k p_k = w S_k - n S_{k+1}$. All that is left to do is to sum over $k$, rearrange, and solve for $\mu$.

• +1. You can actually restrict this to the strict $j \lt w$. I think you could write the last expression as $$\frac{w}{n-w-1}\left(1-\frac{w-1 \choose j}{n \choose j}\right)$$ though it may not be an improvement – Henry Apr 7 '12 at 18:01
• @Henry: (+1) Yes, I like that simplification much better; thanks. I've incorporated it into the answer. The only reason I chose $j \leq w$ was to try to make it clear that the technique followed all the way to the case where there was no truncation at all. :) – cardinal Apr 7 '12 at 18:13
• @Henry: Did you mean to have $n-w+1$ in the denominator? Just double-checking; I think it's a typo, but maybe I missed something. – cardinal Apr 7 '12 at 19:58
• No I didn't - I was trying and failing to copy your earlier $n-w+1$ – Henry Apr 7 '12 at 20:09