Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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}$

share|cite|improve this answer

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}$.

share|cite|improve this answer

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*}$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.