A tricky but intuitive probability problem?

Question

A bag consists of unknown numbers of white and black balls. Randomly take 2 balls out of the bag each time:

If the two balls are of different colour, throw them away;

If the two balls are of the same colour, return them back and add a new ball of colours different from the two into the bag.

Iterate this process until the number of balls in the bag is less than 2. What's the probability that it ends? (So the answer shouldn't depend on the initial distribution of white and black balls?)

A friend of mine asked me the above problem. Unfortunately, I'm not good at probability. But my instinct told me that the probability should be 1. As we are adding a new ball $ \frac {1}{2}$ of the times, removing 2 balls $ \frac {1}{2}$ of the times. Overall, the number of balls should keep declining. How can I make the above reasoning rigorous? Or maybe this is just another common fallacy, the answer should be something different? Sorry if this is a duplicate.

Edit: It seems no matter what the initial distribution of the number of white and black balls are, they will become roughly equal after some amount of time, and then keep declining.

The probability of removing or adding a ball is not necessarily $\frac{1}{2}$: it depends in the number of white balls vs black balls in the bag. — Bram28, Feb 18 '19 at 04:45
Oh, just notice that. But I still think the answer is 1. Say the bag consists of white balls alone, this process will guarantee after some amount of time, the number of white and black balls will be roughly the same, then it will keep declining. — YuiTo Cheng, Feb 18 '19 at 04:48
I share your intuition ... but as you say, making this into a rigorous proof is another matter. — Bram28, Feb 18 '19 at 04:53
You may use double induction on the number of white and black balls in the bag. — little o, Feb 18 '19 at 05:22
Try to figure out that if there were $2$ black balls in the bag then what is probability that the process stops. If that probability is $p$ then I think the required probability would be $\frac {2+p} {3}$. — little o, Feb 18 '19 at 05:42
It is clear that $p < 1.$ Then the required probability is lying in the open interval $\left (\frac 2 3 , 1 \right ).$ — little o, Feb 18 '19 at 06:25
This can be viewed as an absorbing Markov chain https://en.wikipedia.org/wiki/Absorbing_Markov_chain. Let the states be labeled by $(w, b)$ where $w, b$ represent the current number of white and black balls in the bag respectively. Clearly $(1, 0), (0, 1), (0, 0)$ are absorbing states. Next you just need to show that every other states can reach one of these absorbing states in finite number of steps. WLOG says we start from $(w, b)$ and $w > b$. It is easy to construct that we have pick two white balls in first $w-b$ draw and white-black draw in subsequent $w$ draws to reach $(0, 0)$. — BGM, Feb 18 '19 at 07:35
Yes, all absorbing Markov Chain will be absorbed in one of the absorbing states eventually. As mentioned above you just need to make sure it is reachable from any one of the other (transient) states with in a finite step (with a non-zero probability). Not sure if need a more technical arguments as the number of states here is countably infinite. — BGM, Feb 18 '19 at 09:27
@BGM You may consider turning your comment into an answer... — YuiTo Cheng, Feb 18 '19 at 11:39
In a finite absorbing Markov chain in which each transient state can reach an absorbing state, the state will be absorbed eventually with probability $1.$ In the more general case of a Markov chain over an infinite state space, the probability of absorption can be less than $1.$ For example, take a biased random walk over the integers and add an absorbing state at $0$: https://math.stackexchange.com/questions/153123/hitting-probability-of-biased-random-walk-on-the-integer-line — David K, Mar 23 '19 at 16:30

Saša · Answer 1 · 2019-02-18T11:39:37.253

I have made a lengthy series of Monte Carlo experiments and I have not once registered a divergent process. Actually, the process seems to be converging in a fairly predictable way.

Scenario 1

1000 balls in total.
Change the number of white balls from 0 to 1000 in steps of 20.
For each particular count of white balls, repeat experiment 1000 times and calculate the average numbers of steps needed to reach the empty bag.

A fair setup, I think. In total, I run 50.000+ experiments, with different number of white balls and not once the simulation spiraled out of control.

Scenario 2

5000 balls in total.
Change the number of white balls from 0 to 5000 in steps of 100.
For each particular count of white balls, repeat experiment 500 times and calculate the average numbers of steps needed to reach the empty bag.

The process converged every single time.

Some observations:

The shape of the curve is almost the same in both charts.
For a bag with $n$ balls, all of the same color, the expected number of steps is (almost exactly) $3.4\times n$
For a bag with $n$ balls, half of them black/white, the expected number of steps is slightly below $2\times n$
Foll all other white/black setups, the expected number of steps is between the above two extremes.

Code

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class Simulation {
    public static final Random rnd = new Random();
    public static final int BLACK = 0, WHITE = 1;

    private List<Integer> balls = new LinkedList<>();

    public Simulation(int ballCount, int whiteCount) {
        for(int i = 0; i < ballCount; i++) {
            if(i < whiteCount) {
                balls.add(WHITE);
            }
            else {
                balls.add(BLACK);
            }
        }
        Collections.shuffle(balls);
    }

    // returns the number of steps taken before the bag has less than 2 items remaining
    public int run() {
        int steps = 0;
        int n;
        while((n = balls.size()) >= 2) {
            steps++;
            // pick two random balls
            int first = rnd.nextInt(n);
            int second = rnd.nextInt(n);
            while(first == second) {
                second = rnd.nextInt(n);
            }
            // If the two balls are of different color, throw them away;
            if(balls.get(first) != balls.get(second)) {
                balls.remove(Math.max(first, second));
                balls.remove(Math.min(first, second));
            }
            // If the two balls are of the same color, return them back and 
            // add a new ball of color different from the two into the bag.
            else {
                int color = balls.get(first) == WHITE? BLACK: WHITE;
                int position = rnd.nextInt(n);
                balls.add(position, color);
            }
        }
        return steps;
    }

    public static void main(String[] args) {
        // ADJUST THIS: TOTAL NUMBER OF BALLS
        int numBalls = 5000;
        // ADJUST TIHS: NUMBER OF EXPERIMENTS MADE FOR A PARTICULAR COUNT OF WHITE BALLS 
        int numExperiments = 500;
        // ADJUST THIS: WHITE BALL INCREMENT
        int whiteBallIncrement = 100;

        // Lights, Camera, Action...
        for(int numWhites = 0; numWhites <= numBalls; numWhites += whiteBallIncrement) {
            int stepsTotal = 0;
            for(int i = 0; i < numExperiments; i++) {
                stepsTotal += new Simulation(numBalls, numWhites).run();
            }
            int averageSteps = stepsTotal / numExperiments;
            String message = String.format("%d balls, %d whites => %d steps", numBalls, numWhites, averageSteps); 
            System.out.println(message); 
        }
    } 
}

Though not a solution, still appreciate the numerical experiments! — YuiTo Cheng, Feb 18 '19 at 11:39

David K · Accepted Answer · 2019-03-23T19:09:29.487

We could try a proof by contradiction. What are the necessary facts to allow the process not to terminate, and can those facts all be true?

Let $B_n$ be the number of black balls after $n$ steps and $W_n$ the number of white balls after $n$ steps. Let $X_n = (B_{n+1} + W_{n+1}) - (B_n + W_n),$ that is, $X_n$ is the net increase in the number of balls on the $(n+1)$th step.

Given any finite number $N,$ if $B_n + W_n \leq N$ then there is a sequence of $N$ steps or fewer, each step having positive probability, by which the process can terminate from the state $(B_n,W_n).$ For any given state $(B_n,W_n)$ with $B_n + W_n \leq N$ there is therefore a positive probability that the process will terminate. Let $p_0$ be the minimum value of this probability over all states in which $B_n + W_n \leq N$. Clearly $p_0 > 0.$ If we observe the state of the system every $N + 1$ steps, and find that $B_n + W_n \leq N$ occurs $k$ times in the sequence of observations, then the probability that the process will terminate is at least $1 - (1 - p_0)^k.$ In order for this probability to be less than $1,$ there must be an upper bound on $k,$ that is, we cannot infinitely often visit states in which $B_n + W_n \leq N$.

So in order for the process not to terminate, the number of balls must go to infinity as $n$ goes to infinity.

From the state $(B_n,W_n),$ the expected change in the number of balls is \begin{align} E(X_n) &= P(X_n=1) - 2P(X_n=-2) \\ &= \frac{B_n^2 + W_n^2}{(B_n + W_n)^2} - 2\frac{2B_nW_n}{(B_n + W_n)^2}\\ &= 1 - 6\frac{B_n}{B_n + W_n}\left(1 - \frac{B_n}{B_n + W_n}\right). \end{align}

If $\frac14 \leq \frac{B_n}{B_n + W_n} \leq \frac34,$ (or, equivalently, if $\frac14 \leq \frac{W_n}{B_n + W_n} \leq \frac34$; the problem is symmetric for black and white), then $E(X_n \mid (B_n,W_n)) \leq -\frac18.$

Let $M$ be any positive integer and consider the possible trajectories of the process such that $\frac14 \leq \frac{B_n}{B_n + W_n} \leq \frac34$ for every $n > M.$ Under that restriction, the expected number of balls after $n$ steps cannot be greater than the expected value after $n$ steps in a random walk that starts at the maximum possible value of $B_M+W_M$ and has an expected change of $-\frac18$ at each step.

Consider another process that has $B_M+W_M$ balls after $M$ steps and has a uniform expected change of $-\frac18$ in the number of balls at each later step. That process should dominate our process, that is, if there is a probability $p$ of $k$ balls after $n$ steps (with $n > M$) in the uniform process, the probability of $k$ balls after $n$ steps in our process is no greater than $p.$

In the uniform process, the expected number of balls after $n$ steps (if the process continues forever) is $W_M+B_M-\frac18(n - M).$ If $Y_i$ is the number of balls added by that process on step $M + i,$ the Weak Law of Large Numbers says that the probability that the mean value of $Y_i$ is less than $0$ converges to $0$ as $n$ grows without bound. Since $\frac{W_0+B_0+9M/8}n < 1$ for large enough $n,$ the probability that this process has more than $1$ ball remaining after $n$ steps goes to zero. Therefore so does the probability that our process has not ended, conditioned on $\frac{B_n}{B_n + W_n}$ remaining between $\frac14$ and $\frac34.$

So the only possible way for the process to have a non-zero chance to continue forever is if it has a non-zero chance for $\frac{B_n}{B_n + W_n}$ to be outside the interval $\left[\frac14,\frac34\right]$ infinitely often while the sum $B_n + W_n$ goes to infinity.

I think this is ruled out by the Strong Law of Large Numbers but I do not yet have a formal argument for it. (I'm also not completely confident in all the other steps above.) The difficulty is that unlike the usual circumstances in which we apply the Strong Law of Large Numbers, the denominator $B_n + W_n$ is not steadily growing. On the other hand, it does continue growing (if the process does not end) and unlike the usual setting of the Law of Large Numbers, there actually is a bias for each step of the sample mean to go toward the expected value rather than away from it.

A tricky but intuitive probability problem?

2 Answers2