- steps from here is (dropping the subscript on k)
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