Color Balls

A box contains $n$ balls of $n$ different colors. At each step you draw an ordered pair of balls at random, repaint the first to match the color of the second, and return both. How many steps on average until all the balls share a single color?

Reveal solutionHide solution

#Repainting is a voter model

Drawing an ordered pair and repainting the first ball to match the second is the voter model on the complete graph. The box turns a single color exactly once every ball descends from one common origin.

#Trace the colors backward

A ball's color is a copy of whichever ball it last matched. Following those copy links backward in time, the $n$ starting colors form lineages that only ever merge and never split. Represent each surviving lineage by one token, so the token count equals the number of colors still present, falling from $n$ down to $1$ .

#Each merge is geometric

A backward step merges two tokens exactly when its ordered pair lands on two distinct surviving lineages, which with $k$ tokens left happens with probability $\tfrac{k(k-1)}{n(n-1)}$ . So the wait to drop from $k$ tokens to $k-1$ is geometric with mean $\tfrac{n(n-1)}{k(k-1)}$ .

#Telescope

\E[\text{steps}] = \sum_{k=2}^{n} \frac{n(n-1)}{k(k-1)} = n(n-1)\sum_{k=2}^{n}\left(\frac{1}{k-1} - \frac{1}{k}\right) = n(n-1)\left(1 - \frac{1}{n}\right) = (n-1)^2. \tag{1}

Backward in time the colors are tokens that only merge. Dropping from k colors to k-1 takes an expected n(n-1)/(k(k-1)) steps, and the stages telescope to (n-1) squared. The last merge of the final two colors alone is half the wait.

#Read it off

The answer is $(n-1)^2$ . The final merge of the last two colors alone costs $\tfrac{n(n-1)}{2}$ , fully half the wait, since two thoroughly mixed colors are slow to tip over into one.