2
$\begingroup$

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?

  • 0
    I have a questio$n$ about the problem... what is the distribution of W(n+1), given that Wn=k?2012-12-06

1 Answers 1

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