Take the 2-minute tour ×
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.

I'm trying to get my head around this problem, and I think I have a way to think about it.

So let's say I have $a$ white balls and $b$ black balls in a bag initially. I take out a ball and if it's white, I put it back and if it's black, I replace that black ball with a white ball. Let $M_n$ be the expectation of the number of white balls in the bag after $n$ moves.

I want to show

$$M_{n+1} = \left(1-\frac1{a+b}\right)M_n + 1$$

I think a way to do this problem is by writing something like this

Let $w_n =$ number of white balls after $n$ goes.
Let $b_n =$ number of black balls after $n$ goes.

$$M_{n+1} = P(\text{Pick a WhiteBall})(w_n) + P(\text{Pick a BlackBall})(b_n)$$

But I'm not sure where to go from here. In other words, how do I go from probabilities to expectations in a sequence problem such as this?

share|improve this question
    
Don’t you mean that the probability of getting a white ball on the $(n+1)$-st go is $\dfrac{w_n}{w_n+b_n}=\dfrac{w_n}{a+b}$? –  Brian M. Scott Nov 29 '12 at 3:49
    
oh wait, I think the question changed when you edited it - that should be expectation - here let me change it again –  scuba Nov 29 '12 at 3:51
    
also, why does that probability make sense? –  scuba Nov 29 '12 at 3:52
    
Is $M1$ supposed to be $M_1$? If so, why do you have $w_n$ and $b_n$ on the righthand side? In any case, the probability of drawing a white ball isn’t a constant: it depends on the state of the bag, so I don’t understand what you mean by $P(\text{WhiteBall})$ and $P(\text{BlackBall})$. –  Brian M. Scott Nov 29 '12 at 3:59
    
ohhh I see what you're saying - ok then that was a mistake in my thinking - I think it should be Mn+1 = ... , as it is shown now, sorry about that - I was thinking about the expectation wrong and for some stupid reason assumed the probability of picking a white ball would stay constant –  scuba Nov 29 '12 at 4:02

1 Answer 1

The key observation here is that the total number of balls is constant. Then, reasoning with elementary probabilities, we have $M_0 = a$ and from then on recursively

$$ M_{n+1} = \frac{M_n}{a+b} M_n + \left( 1 - \frac{M_n}{a+b} \right) (M_n + 1)$$ or $$ M_{n+1} = \frac{M_n}{a+b} M_n + (M_n + 1) - \frac{M_n}{a+b} M_n - \frac{M_n}{a+b} = M_n \left( 1 - \frac{1}{a+b} \right) + 1,$$ as claimed.

Using mathematical induction we can prove that in fact $$M_n = a+b-b \left( 1- \frac{1}{a+b} \right) ^{n}.$$

share|improve this answer

Your Answer

 
discard

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.