4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ $\infty$, it seems to me that with positive probability the game breaks into 2 distinct sets of sites which cannot exchange rocks, e.g. first move the north pole then the south pole, but maybe you want the same question about when there are no moves left. $\endgroup$
    – user83457
    Commented Mar 28, 2018 at 15:27
  • 1
    $\begingroup$ It sounds as if when a two piles are have a common neighbor (and hence are non-adjacent if $n \gt 3$) AND that central pile disappears then the two neighbors are now considered adjacent. $\endgroup$
    – Aaron Meyerowitz
    Commented Mar 28, 2018 at 17:14

2 Answers 2

Reset to default
4
$\begingroup$

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.$

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ +1 That is very neat. I had got as far as $E(x_1)=0$, $E(x_1,x_2)=x_1x_2$ and $E(x_1,x_2,x_3)=x_1x_2+x_2x_3+x_3x_1$ plus $E(1,1,1,1)=6$ and $E(1,1,1,2)=9$ which is suggestive of your result. I would have thought that, since the state space is finite and the expectations are finite, any solution satisfying the equations will be the unique solution; indeed you could empirically start with any trial solution and apply equations of the form $1+(\sum\cdots)/(2k)$ iteratively to converge on that unique solution. $\endgroup$
    – Henry
    Commented Mar 29, 2018 at 12:25
  • $\begingroup$ And as a pretty corollary: if you start with $n$ individual rocks in a circle, this suggests that the expected number of shifts to reach a single pile is ${n \choose 2}$ $\endgroup$
    – Henry
    Commented Mar 29, 2018 at 12:34
  • 1
    $\begingroup$ @Henry Yes, once you see the results for $2$ and $3$ it is obvious that $E(a,b,c,d)=ab+bc+cd+da.$ Except it must not be obvious because that doesn't even work for $E(1,1,1,1).$ I was pretty surprised. $\endgroup$
    – Aaron Meyerowitz
    Commented Mar 29, 2018 at 13:12
  • $\begingroup$ @Henry Your iterative idea sounds attractive but how would you apply it even for $k+2?$ $\endgroup$
    – Aaron Meyerowitz
    Commented Mar 29, 2018 at 14:22
  • $\begingroup$ Suppose you had five stones, with $a=E(1,1,1,1,1)$, $b=E(1,1,1,2)$, $c=E(1,1,3)$, $d=E(1,2,2)$, $e=E(1,4)$, $f=E(2,3)$, $g=E(5)$ then (using equivalent states) you say $a_{n+1}=1+b_n$, $b_{n+1}=1+\frac14 b_n+ \frac14 c_n+\frac12 d_n$, $c_{n+1}=1+\frac13 d_n+ \frac13 e_n+\frac13 f_n$, $d_{n+1}=1+\frac13 c_n+ \frac13 d_n+\frac13 f_n$, $e_{n+1}=1+\frac12 f_n+ \frac12 g_n$, $f_{n+1}=1+\frac12 e_n+ \frac12 f_n$, $g_{n+1}=0$ then, whatever values you start with, you will iterate towards $(10, 9, 7, 8, 4, 6, 0)$ $\endgroup$
    – Henry
    Commented Mar 29, 2018 at 15:30
3
$\begingroup$

$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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .