Repainting balls until a single colour remains
Question
A box contains 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
. Fix the colour that eventually wins and condition on it: with 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 (simulation agrees, e.g. for ).
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 solutionLessons behind this question
- Markov Chains — Transition Matrices and the Markov Property
- Expectation, Mean, and Variance
- Conditional Expectation and Variance Revisited
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