Random Repainting Process

Expected number of repainting steps until all balls have the same color

Problem

Start with n balls, each having a different color.

At every step:

  1. Choose two distinct balls as an ordered pair.
  2. Repaint the first ball with the color of the second.
  3. Return both balls.

We want the expected number of steps until all balls have one common color.

Key Insight: Look Backward in Time

Tracking the number of balls of every color forward in time is messy.

Instead, trace the balls' ancestry backward.

Suppose ball A was repainted using ball B:

A ← B

After this event, A's color is a copy of B's color.

Therefore, going backward, the ancestry of A merges into the ancestry of B.

two ancestral lineages → one lineage

So the problem becomes:

How long does it take for n ancestral lineages to coalesce into one?

Backward Coalescence

1
2
3
4
5
↓
A repaint causes two ancestral lineages to merge
↓
1
2
3
4

Probability of a Coalescence

1 Suppose there are currently k ancestral lineages.
2 There are
n(n − 1)
possible ordered pairs of distinct balls.
3 To merge two ancestral lineages, the selected pair must correspond to two different current ancestral lineages. There are
k(k − 1)
ordered choices.

Therefore:

P(k → k − 1) = k(k − 1) / [n(n − 1)]

Expected Waiting Time at k Lineages

If each step succeeds with probability

pₖ = k(k − 1) / [n(n − 1)],

then the waiting time is geometric.

Hence:

E[Tₖ] = 1 / pₖ = n(n − 1) / [k(k − 1)]

Add All the Waiting Times

We must go through

n → n−1 → n−2 → ⋯ → 2 → 1.

Therefore:

E[T] = Σ(k=2 to n) n(n−1) / [k(k−1)]

Factor out the constant:

E[T] = n(n−1) Σ(k=2 to n) 1 / [k(k−1)]

The Telescoping Trick

Notice:

1 / [k(k−1)] = 1/(k−1) − 1/k

So:

1/(2·1) + 1/(3·2) + ⋯ + 1/[n(n−1)]

= (1 − 1/2) + (1/2 − 1/3) + ⋯ + (1/(n−1) − 1/n)

= 1 − 1/n

Therefore:

E[T] = n(n−1)(1 − 1/n)
= (n−1)²

Final Answer

E[T] = (n − 1)²

assuming the two selected balls must be distinct.

Try Different Values of n

E[T] = 16

If Selecting the Same Ball Twice Were Allowed

The result changes slightly if the two selections are independent and the same ball may be selected twice.

There would then be n² ordered pairs instead of n(n−1).

P(k → k−1) = k(k−1) / n²

Thus:

E[T] = n² Σ(k=2 to n) 1/[k(k−1)] = n²(1−1/n) = n(n−1)

So:

distinct selections: E[T] = (n−1)²

same ball allowed: E[T] = n(n−1)