Consider a circle with $n$ equally spaced points on it. There are $k$ amoebas on them at clockwise distances $d_1, d_2,\dots d_k$ such that $d_1+d_2+\dots +d_k=n$. At each step an amoeba is picked uniformly at random and moves randomly one step to the left or to the right. If two amoebas meet on the same point, they merge into one amoeba. The process terminates when only one amoeba is left.
If $S(d_1, d_2,\dots d_k)$ is the r.v. for the number of steps until the process terminates, what is $\mathbb{E}[S(d_1, d_2,\dots d_k)]$?
My work so far: So, I've gathered that the order in which the amoebas are picked is not important but I can't really prove it directly. Also, by looking at $n=2,3,4,5$, I managed to make the hypothesis that $\mathbb{E}[S(d_1, d_2,\dots d_k)]=\sum_{i<j} d_i*d_j$. My first idea on how to prove it is by using induction on $k$ for a given $n$ but I couldn't manage to finish a solution. Another way could be to represent the process as a Markov chain but I don't know where to go from there.
Think of this as a random walk on a state $\vec d = (d_1, d_2, \dots, d_k)$ representing the distances between the amoebas. To each state $\vec d$ we associate the two functions $$ f(\vec d) = \mathbb E[S(\vec d)] \text{ and } g(\vec d) = \sum_{i < j} d_i d_j. $$ We want to prove that $f(\vec d) = g(\vec d)$ for all $\vec d$.
By conditioning on the first step, we have for all $\vec d \ne (n)$, $$ f(\vec d) = 1 + \frac1{2k} \sum_{\vec d' \sim \vec d} f(\vec d') $$ where the sum is over all $2k$ states $\vec d'$ that can be reached in one step from $\vec d$, with multiplicity. The state $\vec d = (n)$, in which there is only one amoeba that's $n$ steps from itself around the circle, is the final state of the system we eventually get to, so $f(\vec d) = 0$ at that state.
By some algebra, we can show that for all $\vec d \ne (n)$, $$ g(\vec d) = 1 + \frac1{2k} \sum_{\vec d' \sim \vec d} g(\vec d') $$ also holds: in fact, for each $i$, we have $$ g(d_1, d_2, \dots, d_k) = 1 + \frac12 g(d_1, \dots, d_i + 1, d_{i+1} - 1,\dots, d_k) + \frac12 g(d_1, \dots, d_i - 1, d_{i+1}+1, \dots, d_k) $$ and then we can average over all $i$. (In some cases, we need to make use of a further algebraic property of $g$: that $g(d_1, \dots, d_{i-1}, 0, d_{i+1}, \dots, d_k) = g(d_1, \dots, d_{i-1}, d_{i+1}, \dots, d_k)$.)
Also, $g(\vec d) = 0$ when $\vec d = (n)$, because in that case the sum is empty.
That's the part of the problem which is specific to the amoeba random walk; the rest of the solution is a general idea. The difference $f(\vec d) - g(\vec d)$ is $0$ at the unique absorbing state $(n)$, and satisfies a homogeneous linear recurrence at all other states. We wil conclude that $f(\vec d) - g(\vec d)$ is identically $0$ by the maximum principle. Let $\vec d$ be a state (with at most $k$ amoebas, say) that maximizes the value of $f(\vec d) - g(\vec d)$. Then because we have $$ f(\vec d) - g(\vec d) = \frac1{2k}\sum_{\vec d' \sim \vec d} [f(\vec d') - g(\vec d')] $$ but each of the terms in the average is at most $f(\vec d) - g(\vec d)$, we must have $f(\vec d') - g(\vec d') = f(\vec d) - g(\vec d)$ for all $\vec d' \sim \vec d$. By induction, $f(\vec d') - g(\vec d') = f(\vec d) - g(\vec d)$ for all states reachable in finitely many steps from $\vec d$, but one of those states is $(n)$, for which we know that the difference is $0$. So we must have $f(\vec d) = g(\vec d)$ for all $\vec d$.