Repainting until all match
A bowl holds three balls, each of a different colour. At each step, two of the three balls are picked uniformly at random, and a fair coin decides which of the two is repainted in the colour of the other.
Find the expected number of steps until all three balls have the same colour.
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
What does the bowl look like after the first step?
From two balls of one colour and one of another, what is the chance that the next step finishes the game? What else can happen?
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. After one step the bowl is always “two of one colour, one of another”. From there, each step finishes with the same probability, so the remaining wait is geometric.
Step 1: the first step. Whichever two balls are picked, one takes the other's colour, so two balls now share a colour and the third is different. That takes exactly 1 step.
Step 2: from two plus one. Say the colours are A, A, B. Of the three possible pairs:
- the two A balls: nothing changes;
- an A ball with the B ball (two of the three pairs): with probability the B ball becomes A and the game ends; with probability the A ball becomes B, which gives A, B, B, again two plus one.
So each step ends the game with probability , and otherwise the bowl is still two plus one.
Step 3. The number of further steps is geometric with mean , so the expected total is
In general. With balls of different colours, the expected number of steps is ; for three balls this gives 4.