1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ what do you mean by "we put it and one green ball away" ? $\endgroup$
    – utobi
    Oct 30, 2022 at 21:17
  • $\begingroup$ This seems like some variant of a Pólya urn model $\endgroup$ Oct 31, 2022 at 8:40
  • $\begingroup$ Draw a quick sketch of the moves using (Green, Red) counts as Cartesian coordinates: this will immediately show the problem is a random walk along the line Green = Red + N - 1. Choose a coordinate to parameterize that -- Red will do nicely -- and proceed to solve this simplified but equivalent version of the problem. $\endgroup$
    – whuber
    Mar 26 at 13:36

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ A relevant step in the frog problem was to show that the mean distance from the end is a decreasing function. And as a consequence the probability to remain in the game decreases to zero. This problem is more difficult because there are many positions for which the distance on average increases. In that frog problem there was only one position where the position increases on average, and it was only required to think two steps ahead to show that every two steps the mean position decreases by a factor 1/6. I imagine a similar strategy here but one will have to compute $N$ steps ahead. $\endgroup$ Oct 31, 2022 at 10:07
  • $\begingroup$ Actually the position is an increasing function in every position. It is more likely to get further away from the end than closer. So certainly the probability to finish is not equal to 1. $\endgroup$ Oct 31, 2022 at 10:15
  • $\begingroup$ Working out the case for N = 1 extra green balls, it appears that the probability to finish is actually one. So the argument in my previous comment was not correct. The mistake is probably that while the position is an increasing function, the difference will eventually approach zero and the probability for an infinite path might approach zero. Also, it is only the average position that is increasing, but that doesn't mean that the fraction of the number of paths that do not finish can't approach zero. $\endgroup$ Mar 27 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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