# On the Total Number of Tries Required to have $n$ Successes

The Problem A bag contains $b$ black balls and $w$ white balls. Balls are drawn at random from the bag until the last white ball is drawn. What is the expected number of balls drawn?

My Partial Solution Suppose the balls are lined up in a line and drawn from left to right. The number of balls to the left of the rightmost white ball (say $N$) ranges from $w-1$ to $w+b-1$, the number of balls to right is given by $w+b-N-1$. So, we can calculate the probability of each value of $N$ using the hypergeometric distribution, and we have

$\text{Expected number}=\displaystyle \sum_{k=w-1}^{b+w-1}\frac{\binom{k}{w-1}\binom{w+b-k-1}{0}}{\binom{w+b-1}{w-1}}\cdot\left(k+1\right)$

which requires computation of

$$\displaystyle \sum_{k=w-1}^{b+w-1}\binom{k}{w-1} \cdot \left(k+1\right)$$

which I am unable to do.

Is my method even correct, and is there any easy way to do the problem or compute the sum?

-
Shall we take it that this is without replacement? – Michael Hardy May 8 '12 at 15:24

w balls will always be drawn. For every black ball, let x be the probability that it is drawn. Then the number you want, E = w + bx (using linearity of expectation, make indicator variables for each ball that are 1 if it is drawn else 0).

$x = \frac{w}{w+1}$ (probability that given black ball is not placed after all white balls).

So $E = w + \frac{bw}{w+1}$

-

Let the black balls be labelled from $1$ to $b$. Imagine that we pick all of the balls, one at a time. Define the random variable $X_i$ by $X_i=1$ if black ball with label $i$ is not picked before all $w$ white balls are picked, and by $X_i=0$ otherwise.

Note that $P(X=1)=\frac{1}{w+1}$. For let $S_i$ consist of the $w$ white balls, and black ball $i$. Black ball $i$ is picked at some time after all the white balls precisely if it is the last ball in set $S_i$. Since all orderings of $S_i$ are equally likely, this proability is $\frac{1}{w+1}$. It follows that $E(X_i)=\frac{1}{w+1}$.

Let $X$ be the number of black balls that evade the picking process until all $w$ white balls are picked. Then $X=\sum_1^b X_i$, and therefore $$E(X)=\sum_1^b E(X_i)=\frac{b}{1+w}.$$ Note that the $X_i$ are not independent, but that does not matter for the expectation calculation. The total number of trials in our actual situation is $w+b-X$, so has expectation $w+b-\frac{b}{1+w}$.

-

The (essentially equivalent) approaches given by André and Wonder are simpler, but it is possible to finish off your approach by evaluating the sum:

\begin{align*} \sum_{k=w-1}^{b+w-1}\binom{k}{w-1} \cdot \left(k+1\right)&=\sum_{k=0}^b\binom{w-1+k}{w-1}(w+k)\\\\ &=\sum_{k=0}^b\frac{(w+k)!}{(w-1)!k!}\\\\ &=\sum_{k=0}^b\frac{w(w+k)!}{w!k!}\\\\ &=w\sum_{k=0}^b\binom{w+k}w\\\\ &=w\binom{w+b+1}{w+1}\;, \end{align*}

where the last step uses this identity. However, you have the wrong denominator: it should be $\binom{w+b}w$, the total number of possible ways to place the white balls in the string, since there's no guarantee that the $(w+b)$-th ball is white. Then

\begin{align*} \text{Expected number}&=\displaystyle \sum_{k=w-1}^{b+w-1}\frac{\binom{k}{w-1}\binom{w+b-k-1}{0}}{\binom{w+b}w}\cdot\left(k+1\right)\\\\ &=\frac{w\binom{w+b+1}{w+1}}{\binom{w+b}w}\\\\ &=\frac{w(w+b+1)}{w+1}\\\\ &=w+\frac{bw}{w+1}\;. \end{align*}

-