Probability question about random shuffling of piles of rocks I have $k$ piles of rocks placed on a circle so that every pile has exactly two neighboring piles. We know that initially the piles have $x_1,\dots,x_k$ rocks in each respectively. A monkey plays the following game: at each timestep it picks a random pile, takes a rock from it, and places it in one (again randomly) of its adjacent piles . If a pile becomes empty it disappears and we're left with a game of $k-1$ piles (the monkey can't "revive" an empty pile by placing a rock where it used to be). The game is played until only one pile remains. What is the expected number of timesteps until this happens?
My thoughts so far are that this is like taking a lazy random walk on a graph where each node is a configuration of the $x$ values.
For $k=2$ the solution is simple because it's just a random walk but even for $k=3$ I can't solve it and thus use induction.
I tried thinking of a Markov chain coupling but haven't succeeded for now.
 A: It is an interesting question and must be well known, but not to me. Suppose that the total number of stones is $\sum_1^kx_k=n.$ I am highly confident that the expected number of moves is 
$$E(x_1,x_2,\cdots,x_k)=\sum_{1 \leq i \lt j \leq k}x_ix_j=\frac{(\sum_1^kx_i)^2-\sum_1^kx_i^2}2=\frac{n^2-\sum_1^kx_i^2}2.$$
Observe that this has no respect for the adjacency relations. And indeed, whatever is true remains true if we 
1) randomly choose one pile and move a rock from it to some other random pile. (So the correct answer is a symmetric function of the $x_i$. That cuts things down quite a bit.)
It also remains true if we 
2) assume a circular arrangement but always move a rock from the randomly chosen pile to the clockwise neighbor.    
In either case, or for any (connected) directed graph where each vertex has in-degree=out-degree=$j,$ the expected number of moves is the same.
It doesn't matter if a pile is large or small. As long as that pile is one of $k$ non-empty piles, on the next move its size increases  by $1$ with probability $\frac1k$ ,  decreases by $1$ with probability $\frac1k$ and is unchanged on that move with probability $1-\frac2k.$
Observe too that the formula remains valid if we allow some of the $x_i=0$ with the understanding that any empty pile(s) never have a stone taken from them (of course) nor one added to them.
It is such a simple formula that there is sure to be an elegant proof. All I can say is that a proof by induction on $k$ seems pretty easy:
For $k=1$ pile we need $0$ additional moves.  Now for fixed $n$ and $k \gt 1$ consider the values $E(x_1,x_2,\cdots,x_k)$ with $\sum_1^kx_k=n.$ For convenience we allow at most one of the $x_i$ to be $0.$ By inductive hypothesis we know the value of $E(x_1,x_2,\cdots,x_k)$ in the event that one of the $x_i=0.$ Then we have one or another system of $N$ equations running over the $N$ cases where none of the $x_i=0$ such as
1) $$  E(x_1,\cdots,x_k)=1+\frac{\sum_{i \neq j}E(x_1,\cdots,x_j-1,\cdots ,x_i+1,\cdots ,x_n)}{k(k-1)}$$
OR
2)
$\ E(x_1,\cdots,x_k)=1+\frac{E(x_1-1,x_2+1,x_3\cdots,x_k)+E(x_1,x_2-1,x_3+1,\cdots,x_k)+\cdots +E(x_1+1,x_2,x_3,\cdots,x_k-1)}{k}$
Either way, that system of equations seems sure to determine the various (not already known) $E(x_1,\cdots,x_k)$ uniquely ( this is the detail I didn't pinned down).
There are two points of view. A numerical one useful for guessing the formula and a symbolic one proving that the formula is correct.
To discover the formula (optional for the ultimate proof) one might  do a case explicitly such as $n=13$ and $k=4.$ For this we can reduce the number of unknowns and equations by a factor of nearly $k!$ (at least when $n \gg k$) by observing that the formula does not care about the order of the $x_i$ and hence  only using $E(x_1,x_2,\cdots,x_k)$ and their equations where the $x_i$ are non-decreasing. On the other hand, a computer solving it might not care that much.
However to prove the formula correct (once we know what we wish to prove)  there is really just one equation involving arbitrary non-zero parameters $x_1,x_2,\cdots,x_k.$ Just substitute $E(x_1,x_2,\cdots,x_k)=\sum_{1 \leq i \lt j \leq k}x_ix_j$ into that one equation and verify algebraically that the two sides are equal.
For $k=2$ the full proof is: 
We have $E(a,b)=ab$ because that gives the correct values $E(0,b)=E(a,0)=0$ and  $ab=1+\frac{(a-1)(b+1)+(a+1)(b-1)}2.$ 
A: $k=3$ is a random walk on a triangular grid, bounded by an equilateral triangle.  Each side is a position where one of the piles is empty, at which point it's regressed to an $k=2$ case.  When you move along one of the grid lines, you're removing a stone from the side you're moving away from and adding it to the side you're moving towards.  $k>3$ is similar, but on a $(k-1)$-dimensional simplex (I mean, so is $k<=3$...), and moving so that you're no longer in the interior of the $(k-1)$ simplex but in the interior of one of its bounding $(k-2)$ simplices is a move that removes a pile.
Oh, and note that the number of divisions per side is equal to the total number of stones in the game.
I'm not sure exactly how to solve from there, but I'd be interested if you can find an exact solution for arbitrary $n$.
