Urn problem with replacement of a ball of diferent color

Question

An urn contains ​B black balls and ​W white balls. One ball is ​d​rawn at random and a ball of the opposite color is placed in the urn. W​hat is the mean and variance ​o​f the number of draws necessary to have the urn filled with balls of the same color?

In the first draw, P(black) = B/(B+W) and P(white) = W/(B+W).
If the first draw was black, we now have W+1 white balls and B-1 black balls. If the first draw was white, we now have W-1 white balls and B+1 black balls.

I am confused for even the simple case with W=2 and B=2.

Answer 1

This looks like a textbook style exercise, so I'll give general guidance. This is not an answer to the general question, nor would I say that it's the most efficient way to go about this question, but it might help you get started with thinking about what's going on.

If you're systematic about it you can write sets of recurrence relations in the expected time.

Note that there's only $b+w+1$ possible states, each directly related to the ones either side of it.

So first, let's begin by making a some notation that we can work with.

Let $t(b,w)$ represent the expected time to having only one colour from $B=b$ and $W=w$

Then by the law of total expectation we can write

$t(b,w) = 1+ \frac{b}{b+w} t(b-1,w+1) + \frac{w}{b+w} t(b+1,w-1)$

and this same kind of relationship can be written for any other value for $B$ and $W$. For example we can write:

$t(k,1) = 1 + \frac{k+1}{k} t(k-1,2) + \frac{1}{k} t(k+1,0) = 1+\frac{k-1}{k} t(k-1,2)$, and similarly, or by symmetry, $t(1,h) = 1+\frac{h-1}{h} t(2,h-1)$.

Note that you can also use those equations the other way around.

Now you can write $t(2,2)$ in terms of $t(1,3)$ and $t(3,1)$, and those in turn can be written in terms of known times and $t(2,2)$.

Which simplifies.

Further note that you can do the same thing with other values for $(w,b)$, relating expected time at some point to points further out (toward all one colour or all the other colour), and then push those recursions further (note in particular what happens from $(w,b)$ if you move two steps).

Clearly this sort of calculation "bottoms out" (though there's an extra thing to sort out if $w$ or $b$ are not even). In effect, as you keep trying to push away from $(w,b)$, you either run into the ends, or things you already have in terms of $t(w,b)$.

Consequently, taking this at an elementary level, there's nothing very difficult here, you can just systematically push the expected time calculations out toward each end.

However, you might like to think about where some regularities and simplifications might crop up − or you might just keep trying larger examples until you notice some patterns and show that those hold.

To potentially simplify this still further, you might want to think about what other tools you might bring to bear on this. For example, if you know some things about Markov Chains, you might see what ideas you can bring in from that. If you know about generating functions, you might see what ideas you can bring in from that.

[It's a bit hard to guess what tools you you might have or be expected to use.]