Skip to content

Repainting balls until a single colour remains

Question

A box contains nn balls, each painted a different colour. At each step you draw two balls at random, repaint the second ball in the colour of the first, and put both back. What is the expected number of steps until every ball has the same colour?

Short answer

(n−1)2(n-1)^2. Fix the colour that eventually wins and condition on it: with kk balls of that colour the count moves up or down by one with equal probability, and solving the conditioned birth-death recursion gives an expected absorption time of (n−1)2(n-1)^2 (simulation agrees, e.g. 99 for n=4n=4).

Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 5.1 Markov Chain, 'Color balls', p.112; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Expectation, Variance and Covariance is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free