2
$\begingroup$

This seems like a simple model, but I'm getting a bit stuck on it. Suppose I have an urn with $w$ white balls and $b$ black balls. At each turn, I draw a ball, note its color, and retrieve a ball with the opposite color, paint it the drawn ball's color, and put both back in the urn. (Notice the population is constant). This continues until all balls are the same color.

Here's where I got stuck. Let $b$ denote the number of black balls, $N$ the total number of balls, and $p(b)$ the probability black "fixates" in the urn, given $b$ black balls present.

$$ p(b) = \frac{b}{N}p(b+1) + \frac{N-b}{N}p(b-1)$$

such that $p(N) = 1, p(0) = 0$.

However, this doesn't seem well defined because using this expression, $p(b-1)$ is a function of $p(b)$ creating an infinite recursion.

How am I thinking about this wrong?

$\endgroup$
  • $\begingroup$ If all the balls end up as black (or white) at the end of one step what happens now that there are no balls of opposite color? Does it stay black (or white) forever, so that all black (or white) is an absorbing state? $\endgroup$ – frelk Dec 22 '16 at 21:28
  • $\begingroup$ @frelk yes, that's correct, it would be an absorbing state at the extremes $\endgroup$ – Cam.Davidson.Pilon Dec 22 '16 at 21:30
1
$\begingroup$

You are not thinking about it wrong. It just turns out to be a Markov chain (which have infinite recursion) or a form of a random walk (also can be infinite).

I would probably approach this as a Markov chain, then you only need to work out the probabilities of one step, then use the MC theory/methods to work out the long term/infinite probabilities.

$\endgroup$
  • $\begingroup$ This is really good, and obvious, advice. I was so use to my tool of DP I forgot about the more general MC toolset. $\endgroup$ – Cam.Davidson.Pilon Dec 22 '16 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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