Another colored balls puzzle

Question

This is a puzzle a colleague asked me recently.

Imagine you have $n$ balls in a bag that are colored from $1$ to $n$. At each turn you take two balls at random out that have different colors and color one the color of the other. You then put them both back in the bag. What is the expected number of turns before all the balls have the same color?

The pair of balls you choose is uniformly selected from the set of all pairs of different-colored balls. You choose uniformly at random whether to paint the first the same as the second or vice versa.

Answer 1

I think you can verify Greg Martin's answer using indicator variables and linearity of expectation.

Let the random variable $X_i$ be the number of steps where one of the balls has the $i$th color before the $i$th color either disappears or becomes the only color.

The expected value of $X_i$ is as in the Gambler's Ruin, that is, $1 \cdot (n-1) = n-1$.

Each step involves two colors, hence the time to a single color is $\frac{1}{2} \sum X_i$.

The $\binom{n}{2}$ answer follows.

Answer 2

It seems there is little to add after Russ Woodroofe's nice answer, but anyway: If at each time $t=0,1,2,\dots$, we draw two balls without conditioning on them having different colors, then the probability of drawing two different colors at time $t$ is $$\left(1-\frac1{\binom{n}2}\right)^t.$$ This is because the number of pairs of balls of different color will stay the same every time we draw two balls of the same color, but decrease by one in expectation every time we draw two balls of different colors (that pair will become of the same color and everything else cancels!).

Running the process to infinity, the expected total number of times we draw balls of different color is $$\sum_{t=0}^\infty \left(1-\frac1{\binom{n}2}\right)^t = \binom{n}2.$$

Answer 3

I've calculated rigorously that the expectations for $n=1,2,3,4$ are $0,1,3,6$ respectively. For example, when $n=4$:

• One turn brings the balls to a 211 state (meaning 2 balls of one color and 1 ball each of two more colors).
• From a 211 state, there is a $2/5$ probability of going to another 211 state, a $2/5$ probability of going to a 31 state, and a $1/5$ probability of going to a 22 state.
• In other words, there is a $2/5$ probability of staying in the 211 state and a $3/5$ probability of leaving it; the expected number of turns it takes to leave the 211 state is thus $1/(1-2/5) = 5/3$. When it does leave, there's a $2/3$ probability of being in a 31 state and a $1/3$ probability of being in a 22 state.
• By Gambler's Ruin, the expected number of turns to go from the 22 state to the 4 state is $2(4-2)=4$, while the expected number of turns to go from the 31 state to the 4 state is $3(4-3)=3$.
• Therefore, the total expected number of turns for the $n=4$ game is $1 + 5/3 + (\frac23\cdot 3 + \frac13\cdot 4) = 6$.

Moreover, I've run simulations for $n=5,6,7$. The data strongly suggests that the expectations are $10,15,21$ respectively.

I am thus persuaded to conjecture that the expected stopping time for $n$ balls in general is exactly $\binom n2 = n(n-1)/2$.

Answer 4

Let $B_i$ denote the number of balls of color $i$ ($i=1,\ldots,n$) after some turns, and define a quantity $$ S=\sum_i B_i^2. $$ Suppose that on the next turn, we draw two balls of colors $j\neq k$, and choose one at random to receive the color of the other. The expected value of $S$ after this turn is $$ \frac{1}{2}\left(\sum_{i\neq j,k}B_i^2+(B_j+1)^2+(B_k-1)^2\right)+\frac{1}{2}\left(\sum_{i\neq j,k}B_i^2+(B_j-1)^2+(B_k+1)^2\right)=\sum_i B_i^2 +2. $$ The expected value of $S$ increases by $2$ each turn. The initial value of $S$ is $n$, and when all balls are the same color the value of $S$ is $n^2$, so the expected number of turns is $$ \frac{n^2-n}{2}. $$