Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

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.

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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
up vote 7 down vote accepted

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.

share|cite|improve this answer
Thanks! I didn't think of using indicators before! – wircho Oct 26 '11 at 22:09

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.

share|cite|improve this answer
Great! Thanks! Definitely better than brute force :) – wircho Oct 26 '11 at 22:10

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