# What is the probability that the process stops?

Suppose there are $$1$$ white and $$2$$ black balls in a bag. We take two balls at a time at random from the bag. If the two balls are of different colour we throw them away but if they are of the same colour then we return them back in the bag and also add a new ball of different colour in the bag. We iterate this process unless the number of balls in the bag is less than $$2.$$ Then what is the probability that this process stops?

Thank you very much.

EDIT $$:$$

If $$\tau$$ is the stopping time then I found that $$P(\tau = 1) = 0,P(\tau = 2) = \frac 1 2,P(\tau = 3) = 0, P(\tau = 4) = \frac {1} {2^2}, P(\tau = 5) = \frac {1} {2^2} \cdot \frac {1} {3^2}, P(\tau = 6) = \frac {1} {2} \cdot \frac {1} {3^3}.$$

But I can't find any pattern to find $$P(\tau = n).$$ It is clear that the required probability is $$\sum\limits_{n=1}^{\infty} P(\tau = n).$$ How to find pattern to evaluate those probabilities?

• When you say "add a ball of a different color" do you mean if you grabbed two white balls you add a black ball and if you grabbed two black balls you add a white ball, or that you add an entirely new color altogether, e. g. blue? – orlp Feb 18 at 7:10
• No the previous one. If you grabbed two white balls you add a black ball and if you grabbed two black balls then you add a white ball. – Dbchatto67 Feb 18 at 7:14
• Would you please share me your intuition @orlp? – Dbchatto67 Feb 18 at 7:16

Let the situation when there are $$n_w$$ white and $$n_b$$ black balls in the bag correspond to a point with coordinates $$(n_w, n_b)$$ on a plane.

From the point $$(n_w, n_b)$$ we can jump to one of the following three points:

$$(n_w-1, n_b-1)$$ - if balls of different colors were fetched

$$(n_w+1, n_b)$$ - if two black balls fetched

$$(n_w, n_b+1)$$ - if two white balls fetched

Our point roams around the plain until it either comes too close to $$(0, 0)$$ or moves away to infinity.

My intuition tells that the point would not run away to infinity.

If there are much more white balls than black balls than the number of black balls would increase, so the ratio $$n_w/n_b$$ would approach 1.

If we have a large number of black balls and approximately the same number of black balls, than with probability 1/2 the number of balls would decrease by 2, and with probability 1/2 it would increase by 1. So, the total number of balls tends to decrease.

As the point would not run away to infinity it would roam around $$(0, 0)$$ indefinitely and sooner or later with probability 1 would hit one of the final points: (0, 0), (0, 1), (1, 0).

More rigorous proof would be to analyze the behavior of function $$max(n_b, n_w)$$. After each step it can either increase or decrease by 1, or remain unchanged. It is easy to prove that probability it decreases is always higher than the probability it increases. That means that our point would not run away to infinity.

I understand this is not a rigorous proof, but the question is interesting and there was no other answers for a while.

So, the final answer is: the probability iterations stop is 1.

Simple computer simulation confirms this answer.

• That is not actually a textbook problem @lesnik. That question actually came into my mind when I was sleeping at night after lots of problem solving in probability before the day of my exam. – Dbchatto67 Feb 19 at 7:54