# Expectation of number of trials before success in an urn problem without replacement [duplicate]

Possible Duplicate:
Expected number of draws until the first good element is chosen

An urn contains $b$ blue balls and $r$ red balls. Balls are removed at random without replacement until the first blue ball is drawn. What is the expectation of the total number of balls drawn? The answer should be $\frac{b+r+1}{b+1}$ but I have not been able to prove it.

I know that this seems like an easy/classic problem but I tried brute force (definition of expectation) and got a sum that I'm not able to simplify. Then I tried looking up well known distributions but none of them works for this problem.

-

## marked as duplicate by Srivatsan, Mike Spivey, Byron Schmuland, Ｊ. Ｍ., t.b.Oct 26 '11 at 5:47

This very problem was asked a few days ago: Expected number of draws until the first good element is chosen. –  Mike Spivey Oct 26 '11 at 4:11
@Mike So why not close as duplicate? –  Srivatsan Oct 26 '11 at 4:18
@Srivatsan: Probably should, but the answers here are better! Byron's answer is the same as mine on the other question, but your approach doesn't appear there. –  Mike Spivey Oct 26 '11 at 4:20
@Mike I just voted to close as duplicate. Neither of the current answers should be affected by closure. And of course, further posters can post their answers directly over there. –  Srivatsan Oct 26 '11 at 4:24
@Srivatsan: All of that is true. O.K., I've added my vote as well. –  Mike Spivey Oct 26 '11 at 4:28

For $1\leq i\leq r$, let $Z_i$ be the indicator random variable that gives 1 if the $i$th red ball is drawn before any blue ball and 0 otherwise. Then $$\mathbb{E}(\mbox{number of balls drawn})=1+\sum_{i=1}^r \mathbb{E}(Z_i)=1+r\left({1\over b+1}\right).$$ The "1" comes from the terminating blue ball. The expression $1\over b+1$ is the probability that the $i$th red ball is drawn before all the blue balls. The reason for $1\over b+1$ is that, among the set consisting of all the blue balls plus the $i$th red ball, any of those is equally likely to be drawn first.
Here's one approach perhaps better than brute-force, but not as elegant as Byron's answer ;). Denote the expectation is $E(b,r)$. Conditioning on whether the first drawn ball is blue or red, we can write: $$E(b,r) = \color{Blue}{\frac{b}{b+r} \cdot 1} + \color{Red}{\frac{r}{b+r} \cdot (1+E(b, r-1))}, \tag{1}$$ where the color of the term reveals which of the two events we are conditioning on. (While conditioning on red, the factor $1+E(b, r-1)$ stands for the current trial plus the expected number of further trials to get success. Note that, at this stage, we picked a red ball from the urn; so the urn contains $b$ blue balls and $r-1$ red balls.)
We can rewrite $(1)$ as $$E(b,r) = 1 + \frac{r}{b+r} \cdot E(b, r-1).$$ Now, we can guess the correct answer (either by computing the first few values or by peeking at the answer) to be $$E(b,r) = \frac{b+r+1}{b+1},$$ and verify it using induction on $r$. :-) Note that, for the purposes of induction, we can regard $b$ as a fixed constant, and $r$ as the variable.