Repainting Balls Until One Color Remains
A box contains $n$ balls, each a different color. At every step you draw a ball uniformly at random, then draw a second ball uniformly at random from the remaining $n - 1$, repaint the first ball with the color of the second, and return both to the box. You repeat until every ball in the box has the same color.
Show that the expected number of steps until all $n$ balls share one color is $(n - 1)^2$.
Hints
- By symmetry each of the $n$ original colors is equally likely to be the survivor. So the expected time equals the expected time *conditional on* a particular color (say red) winning.
- Let $i$ be the number of red balls. Unconditionally, $i$ moves up or down by one with equal probability $p_i = \dfrac{i(n-i)}{n(n-1)}$ each. Conditioning on red winning (which from $i$ reds has probability $i/n$) re-weights these to up: $p_i \cdot \frac{i+1}{i}$ and down: $p_i \cdot \frac{i-1}{i}$.
- Write $E_i$ for the conditional expected remaining steps and set $G_i = i E_i$. The recursion becomes $G_{i+1} - 2G_i + G_{i-1} = -\dfrac{n(n-1)}{n-i}$ with $G_0 = G_n = 0$; sum the second differences to get $G_1 = (n-1)^2$.
Worked Solution
How to Think About It: Tracking the full color configuration is hopeless. Instead pick one color, say red, and track only the number of red balls $i$. That count moves by $\pm 1$ with equal probability, so it is a martingale, and it is absorbed at $0$ (red disappears) or $n$ (red takes over). The unconditional absorption time of the whole system is the time until *some* color takes over, which is awkward to write from the red count alone; but by symmetry we may condition on red being the winner, and the conditioned chain is a clean birth-death process.
Approach: (1) Show each color wins with probability $1/n$, so the unconditional expected time equals the expected time conditional on red winning. (2) Derive the transition probabilities of the red count conditioned on red winning. (3) Solve the resulting linear recursion with a telescoping substitution.
Formal Solution:
*Step 1 -- Unconditional dynamics of the red count.* Let $X_t$ be the number of red balls after $t$ steps, $X_0 = 1$. In one step the count changes only if the two drawn balls have different colors and exactly one of them is red. Red count goes up by one if the first ball is non-red and the second is red: probability $\frac{(n-i)}{n}\cdot\frac{i}{n-1}$. It goes down by one if the first is red and the second is non-red: probability $\frac{i}{n}\cdot\frac{n-i}{n-1}$. So with $p_i = \dfrac{i(n-i)}{n(n-1)}$,
$$P(i \to i+1) = P(i \to i-1) = p_i, \qquad P(i \to i) = 1 - 2p_i.$$
*Step 2 -- Which color wins.* $X_t$ is a bounded martingale absorbed at $0$ or $n$, so by optional stopping $P(\text{red wins} \mid X_0 = i) = i/n$; from $i = 1$ it is $1/n$, the same for every color. The total time $T$ until the box is monochromatic satisfies
$$E[T] = \sum_{c} P(c \text{ wins})\, E[T \mid c \text{ wins}] = E[T \mid \text{red wins}],$$
since all $n$ conditional expectations are equal by symmetry.
*Step 3 -- The conditioned chain (Doob $h$-transform).* Conditioning on red winning multiplies each transition probability $i \to j$ by $h(j)/h(i)$ with $h(i) = i/n$. Hence, given red wins,
$$P(i \to i+1) = p_i\,\frac{i+1}{i}, \qquad P(i \to i-1) = p_i\,\frac{i-1}{i}, \qquad P(i \to i) = 1 - 2p_i,$$
which indeed sum to 1. Note the conditioned chain can never step from $1$ to $0$.
*Step 4 -- Recursion for the expected remaining time.* Let $E_i = E[\text{remaining steps} \mid X = i, \text{red wins}]$, with $E_n = 0$. First-step analysis:
$$E_i = 1 + p_i\frac{i+1}{i}E_{i+1} + p_i\frac{i-1}{i}E_{i-1} + (1 - 2p_i)E_i.$$
Rearranging, $2p_i E_i = 1 + \dfrac{p_i}{i}\big[(i+1)E_{i+1} + (i-1)E_{i-1}\big]$. Multiply by $i/p_i$ and set $G_i = iE_i$ (so $G_0 = 0$ and $G_n = 0$):
$$2G_i = \frac{i}{p_i} + G_{i+1} + G_{i-1} = \frac{n(n-1)}{n-i} + G_{i+1} + G_{i-1}, \qquad 1 \le i \le n-1.$$
*Step 5 -- Telescope.* Let $d_i = G_i - G_{i-1}$. The recursion says $d_{i+1} = d_i - \dfrac{n(n-1)}{n-i}$, so
$$d_i = d_1 - n(n-1)\sum_{k=1}^{i-1}\frac{1}{n-k}.$$
Since $G_n - G_0 = \sum_{i=1}^{n} d_i = 0$,
$$n\,d_1 = n(n-1)\sum_{i=1}^{n}\sum_{k=1}^{i-1}\frac{1}{n-k} = n(n-1)\sum_{k=1}^{n-1}\frac{n-k}{n-k} = n(n-1)(n-1),$$
because each $k$ appears for the $n - k$ values $i = k+1, \ldots, n$. Hence $d_1 = (n-1)^2$.
*Step 6 -- Conclude.* $E_1 = G_1 = d_1 = (n-1)^2$, so
$$E[T] = E[T \mid \text{red wins}] = E_1 = (n-1)^2.$$
*Sanity checks.* $n = 2$: one step always suffices, and $(2-1)^2 = 1$. $n = 3$: the exact absorption time of the three-ball chain is $4 = (3-1)^2$.
Answer: The expected number of steps is $(n-1)^2$.
Intuition
The number of balls of any fixed color is a martingale (each step is equally likely to add or remove one), so the probability that a given color takes over is its current share, $i/n$. Because every color is equally likely to win, the unconditional expected absorption time equals the expected time along paths where a chosen color wins, and that conditioned chain is a tractable birth-death process. The exact answer $(n-1)^2$ is the same as the Moran model's fixation time in population genetics; the "condition on the winner, then use the Doob h-transform" trick is a staple for absorption-time questions whenever the martingale that identifies the winner is obvious.