This article is from the Puzzles FAQ,
by Chris Cole email@example.com and Matthew Daly
firstname.lastname@example.org with numerous contributions by others.
An urn contains n balls of different colors. Randomly select a pair, repaint
the first to match the second, and replace the pair in the urn. What is the
expected time until the balls are all the same color?
If the color classes have sizes k1, k2, ..., km, then the expected number of
steps from here is (dropping the subscript on k):
2 k(k-1) (j-1) (k-j)
(n-1) - SUM ( ------ + SUM --------------- )
classes, 2 1<j<k (n-j)
The verification goes roughly as follows. Defining phi(k) as (k(k-1)/2 +
sum[j]...), we first show that phi(k+1) + phi(k-1) - 2*phi(k) = (n-1)/(n-k)
except when k=n; the k(k-1)/2 contributes 1, the term j=k contributes
(j-1)/(n-j)=(k-1)/(n-k), and the other summands j<k contribute nothing.
Then we say that the expected change in phi(k) on a given color class is
k*(n-k)/(n*(n-1)) times (phi(k+1) + phi(k-1) - 2*phi(k)), since with
probability k*(n-k)/(n*(n-1)) the class goes to size k+1 and with the same
probability it goes to size k-1. This expected change comes out to k/n.
Summing over the color classes (and remembering the minus sign), the
expected change in the "cost from here" on one step is -1, except when we're
already monochromatic, where the handy exception k=n kicks in.
One can rewrite the contribution from k as
(n-1) SUM (k-j)/(n-j)
which incorporates both the k(k-1)/2 and the previous sum over j.
That makes the proof a little cleaner.