Red and Green Ball Games

Question

Suppose we have a bag which has 1 red ball and N green balls. We randomly draw a ball from the bag: if this is red, we do not put it back and take one green ball from the bag and discard it too; if this is green, we put it back and put one red ball and one green ball into the bag. This will guarantee that we will always have N-1 more green balls than red balls every time. The game will stop when there are no red balls left. What's the probability that the game will stop?

Answer 1

Partial answer:

If you rephrase your problem it becomes much easier to comprehend. Here is how I would write it down:

---

Suppose we have a bag which has x red balls and x+N green balls.

Each turn we randomly draw a ball from the bag:

• If this is red, we discard it along with another green ball from the bag.

  Now we will have x-1 red balls and x+N-1 green balls in the bag.

• If this is green, we put it back and put one red ball and one green ball into the bag.

  Now we will have x+1 red balls and x+N+1 green balls in the bag.

This will guarantee that we will always have N more green balls than red balls every time. In this alternative representation we have a variable $x$, with probability $\frac{x}{x+x+N}$ it decreases by 1 and with probability $\frac{x+N}{x+x+N}$ it increases by 1.

The game will stop when there are no red balls left or when $x=0$. What's the probability that the game will stop of we start with $x = 1$?

This situation is similar to The Dead Drunk Man but the probability of a step is not exactly 0.5 (only it's limit for $x \to \infty$) and variable instead.

---

This you might solve by using some sort of relation between the probabilities to stop when $x = 2$, $x = 3$, etc.

Let's define $P(k,m)$ be the probability that the game stops if we start with $k$ red balls and $k+m$ green balls.

If you are at some value $k$ then you have a possibility that you increase or decrease. The number $k$. And the probability to stop will be based on the values in those next cases.

$$P(k,m) = \frac{k}{2k+m} P(k-1,m) + \frac{k+m}{2k+m} P(k+1,m)$$

We can fill in $P(0,m) = 1$ but that is not enough to solve it. This is similar to the frog problem described here: The frog problem with negative steps That problem could be solved by using a difference $Q(k,m) = P(k,m) - P(k-1,m)$ (see fuether below) or by having a additional stopping condition at the other end ($k=0$ and also $k=K$) and let take the limit when that condition goes towards infinity $K \to \infty$.

You might possibly solve this as a diffusion problem or Markov chain with an absorbing boundary at $k=0$.

---

Working out the problem with the difference

In this case we might do something like define $$P(k,m)-P(k-1,m) = \frac{k+m}{2k+m} \left(P(k+1,m) - P(k-1,m) \right)$$

And with $Q(k,m) = P(k,m) - P(k-1,m)$

$$ Q(k+1,m) = \frac{k}{k+m} Q(k,m)$$

And if we define $Q_1 = Q(1,m)$, then

$$ Q(k,m) = Q_1 \prod_{i = 1}^k \frac{i-1}{i+m-1} = Q_1 {k-1+m \choose k-1}^{-1}$$

and $$P(k,m) = 1+\sum_{i=1}^k Q(k,m) = 1+Q_1 \sum_{i=0}^{k-1} {i+m \choose i}^{-1} = 1+Q_1 \frac{m\left(1- {k+m \choose k+1}^{-1}\right)}{m-1 }$$

(I am not sure about the last step, but Wolfram alpha tells this)

The limit of this is $\frac{m+1}{m-1}$ and because $P(k,m) \in [0,1]$ we have a limit for $Q_1 \geq -\frac{m-1}{m+1}$ and $$P(1,m) \geq \frac{2}{m+1}$$.

A special case is $m = 1$ (we start with 1 additional green ball), then the lower limit equals one and so then the probability to return is 1. For other cases $m > 2$, I am not sure.