A balls-and-colors problem, supposedly elegant solution that needs to be explained further Here's a question asked on MO:
https://mathoverflow.net/questions/41939/a-balls-and-colours-problem

A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour of the first. Then, you put both balls back into the box. What is the expected number of times this needs to be done so that all balls in the box have the same colour?

Here is a supposedly elegant answer given by Ori Gurel-Gurevich:
https://mathoverflow.net/a/41985/169482

It can probably be done by looking at the sum of squares of sizes of color clusters and then constructing an appropriate martingale. But here's a somewhat elegant solution: reverse the time!
Let's formulate the question like that. Let $F$ be the set of functions from $\{1,\ldots,n\}$ to $\{1,\ldots,n\}$ that are almost identity, i.e., $f(i)=i$ except for a single value $j$. Then if $f_t$ is a sequence of i.i.d. uniformly from $F$, and
$$g_t=f_1 \circ f_2 \circ \ldots \circ f_t$$
then you can define $\tau= \min \{ t | g_t \verb"is constant"\}$. The question is then to calculate $\mathbb{E}(\tau)$.
Now, one can also define the sequence
$$h_t=f_t \circ f_{t-1} \circ \ldots \circ f_1$$
That is, the difference is that while $g_{t+1}=g_t \circ f_{t+1}$, here we have $h_{t+1}=f_{t+1} \circ h_t$. This is the time reversal of the original process.
Obviously, $h_t$ and $g_t$ have the same distribution so
$$\mathbb{P}(h_t \verb"is constant")=\mathbb{P}(g_t \verb"is constant")$$
and so if we define $\sigma=\min \{ t | h_t \verb"is constant"\}$ then $\sigma$ and $\tau$ have the same distribution and in particular the same expectation.
Now calculating the expectation of $\sigma$ is straightforward: if the range of $h_t$ has $k$ distinct values, then with probability $k(k-1)/n(n-1)$ this number decreases by 1 and otherwise it stays the same. Hence $\sigma$ is the sum of geometric distributions with parameters $k(k-1)/n(n-1)$ and its expectation is
$$\mathbb{E}(\sigma)=\sum_{k=2}^n \frac{n(n-1)}{k(k-1)}= n(n-1)\sum_{k=2}^n \frac1{k-1} - \frac1{k} = n(n-1)(1-\frac1{n}) = (n-1)^2 .$$

However, I don't understand this very terse answer at all, and so was wondering if anyone could explain it to us who are less familiar with the tools.

*

*Why is reversing the time key here? Why can't we just straightforwardly apply what's done in the last paragraph of the solution ("reverse time") to the regular "forward time" stuff?

*I don't understand the last paragraph at all, can someone explain it with more detail?

Peter Shor offered the following comment on MO as clarification:

Aha! I now understand Ori's answer. At time $t$, considering all steps from step $t$ to the end, there will be $k$ balls whose colors are mapped to all the other balls at the end. Considering time step $t-1$, the only way to reduce $k$ is to choose two of these $k$ influential balls, and have the color of one mapped to that of another. This gives the recursion in his answer. Very nice, although it could be explained better.

But I don't understand Peter's clarification either!
So I'm wondering if anyone could explain Ori's answer in a more user-friendly way, so low-level students like myself can understand (and not just the research mathematicians of MO).
 A: This isn't a standalone answer but a supplement to Ori's.
I think his answer proceeds fairly clearly if you take it literally and don't try to relate it to the word problem, but what's left out is an explanation of why his $g_t$ sequence models the desired process. In particular, it composes the "almost identity" functions in reverse order: he extends the $g_t$ sequence by precomposing $f_{t+1}$ with it, even though the $(t+1)$th coloring operation happens after the first $t$. Why is that what we want?
Let's work it out: If $g_{t}(x)$ is the color of ball $x$ after $t$ steps, and step $t+1$ copies the color of ball $i$ onto ball $j$ (modeled by $f_{t+1}(j)=i$ and $f_{t+1}(x)=x$ for $x\neq j$), then the color of ball $j$ after $t+1$ steps is whatever color ball $i$ was after $t$ steps, i.e. $g_{t+1}(j)=g_t(i)=g_t(f_{t+1}(j))$, and we have $g_{t+1}=g_t \circ f_{t+1}$ as claimed. This justifies the given definition of $g_t$, so we can write "the number of steps needed to make all the balls the same color" as $\min \{t: g_t \text{ is a constant function}\}$.
Once we've translated the problem into an abstract one about function compositions, the rest of the solution doesn't require thinking about ball colorings. We notice that $g_t$ and $h_t$ (viewed as function-valued random variables) have the same distribution, since they're both just a composition of $t$ randomly-chosen functions from $F$. Therefore,
$$\Bbb E(\min \{t: g_t \text{ is constant}\})=\Bbb E(\min \{t: h_t \text{ is constant}\})=\Bbb E(\min \{t: h_t \text{ has exactly one distinct value}\}).$$
We proceed by reasoning about how the number of distinct values in the range of $h_t$ is affected by composing $f_{t+1}$ with it. This turns out to be easier to analyze than for $g_t$ because now we're "post-composing". We can never increase the number of distinct values by applying another function, and we can only decrease it (by 1) by applying an $f$ that merges two existing distinct values. The probability of picking such an $f$ when $h_t$ has $k$ distinct values is $\frac{k(k-1)}{n(n-1)}$, so the waiting time for each decrease is a geometric random variable, and the rest of the calculations follow.
As I wrote in some comments on Mike's PSE answer, what we're really doing here by reversing the composition order is looking at the effect of prepending a step (to a sequence of steps in the original process, hence "reversing time") on the number of "influential balls"—those whose colors are carried through the whole sequence. (The distinct values in the range of $h_t$ are the identities of these influential balls for the step sequence $f_t,...,f_1$.) That's what Peter Shor's comment is saying.
