# Expectations in sequences

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?

-
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

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

-