A Markov Chain Problem.(Change the color of ball) There are $n$ different color balls in a box. Take two balls in turns, and change color of the second ball to the first. (This is one operation). Let $k$ be the (random) number of operations needed to change all $n$ balls to same color.
How to calculate the expected value of $k$?
 A: Here's a rough estimate which may give an idea of how to get a proper answer.
Let $X_i(t)$ be the number of colors such that there are $i$ balls of that color. Let the level at time $t$, denoted by $L(t)$, be the largest $i$ such that $X_i(t)>0$. Suppose $L(t)=i$. We want the probability that $L(t+1)=i+1$. 
At time $t$, there are $i X_i(t)$ balls of such colors. So $L(t+1)=i+1$ if and only if the first draw is of one of these colors and the second is of any different color. This will happen with probability $\frac{i X_i(t) (n-i)}{n(n-1)}$. Now notice that for $i>1$, when we reach level $i$, $X_i=1$. So the probability that $L(t+1)=i+1$ given that $X_i(t)=1$ is $i$ is $\frac{i (n-i)}{n(n-1)}$. If we neglect the possibility that $X_i$ decreases or increases before the level reaches $i+1$, we get a rough estimate of the expected time:
$$E \tau \approx 1 + \sum_{i=2}^{n-1} \frac{n(n-1)}{i (n-i)}$$
This is exact for $n=2$ and $n=3$, as is fairly straightforward to check. It is not exact for $n=4$; the above suggests the value $8$, but the actual value is $9$, so there is a significant effect of the level dropping back to $2$ after reaching $3$. Presumably it is not exact for higher $n$ either.
