Average number of trials until drawing $k$ red balls out of a box with $m$ blue and $n$ red balls

Question

A box has $m$ blue balls and $n$ red balls. You are randomly drawing a ball from the box one by one until drawing $k$ red balls ($k < n$)? What would be the average number of trials needed?

To me, the solution seems to be

$$\sum_i i * \frac{\mbox{the number of cases where k-th red ball is picked at i-th trial}}{\mbox{the number of cases where k-th red ball is the last ball picked}}$$

the denometer seems to be

$$\sum_{r=k-1}^{m-1} \binom{r}{k-1} = \binom{m}{k-1} $$

But, I have a difficulty of deriving a closed form formula for the numerator which seems to be $\sum_{i=k}^{m-1} i \binom{i-1}{k-1}$.

I would appreciate if somebody helps me on that.

Answer 1

The fastest approach in the without replacement case may be to say that any individual blue ball has probability $\dfrac{k}{n+1}$ of being drawn before the $k$th red ball: it is equally likely to be in any of the gaps before, between or after the red balls.

So by linearity of expectation you expect $\dfrac{km}{n+1}$ blue balls to be drawn before the $k$th red ball.

This makes an expectation of $k\left(1+\dfrac{m}{n+1}\right)$ balls drawn in total when the $k$th red ball appears.

Answer 2

For your sum, we have $$\sum_{i=k}^{m-1} i \binom{i-1}{k-1} = \sum_{i=k}^{m-1} \frac{i!}{(k-1)!(i-k)!} = k\sum_{i=k}^{m-1} \frac{i!}{k!(i-k)!} = k \sum_{i=k}^{m-1} \binom{i}{k}.$$ By the hockey stick formula, this simplifies further: $$k \sum_{i=k}^{m-1} \binom{i}{k} = k\sum_{i=k}^{m-1}\binom{i}{i-k} = k\sum_{i=0}^{m-1-k}\binom{i+k}{i} = k\binom{m}{m-k-1} = k\binom{m}{k+1}.$$