3
$\begingroup$

This is a followup to A very simple discrete dynamical system with pebbles

The setup: we have slots $n$ slots labeled $1, \ldots, n$ and $k$ pebbles, each of which is initially placed in some slot. Now the pebbles want to space themselves out as evenly as possible, and so they do the following. At each time step $t$, each pebble moves to the slot closest to the halfway point between its neighboring pebbles; if there is a tie, it chooses the slot to the left. The leftmost and rightmost pebbles apply the same procedure, but because they only have one neighbor, they imagine that there are slots numbered $0$ and $n+1$ with pebbles in them.

Formally, numbering the pebbles $1, \ldots, k$ from left to right, and letting $x_i(t)$ be the slot of the $i$'th pebble at time t, we have $$ x_i(t+1) = \lfloor \frac{x_{i-1}(t)+x_{i+1}(t)}{2} \rfloor, i = 2, \ldots, k-1$$ $\lfloor \cdot \rfloor$ rounds down to the closest integer. Similarly, $$ x_1(t+1) = \lfloor (1/2) x_2(t) \rfloor, x_k(t+1) = \lfloor \frac{x_{k-1}(t) + (n+1)}{2} \rfloor.$$

My question: I feel that it is true that (i) after sufficiently many iterations (ii) for large $n$ this dynamical system will spend all of its time in states which are approximately equispaced. Can this statement be made precise?

Note: My earlier question ( A very simple discrete dynamical system with pebbles) asked about one way to make the above statement precise, which turned out not to work.

  • 0
    Before thinking further about the problem: I wonder if you get rid of the boundary assumption by making the universe compact. That is, imagine the slots going around a circle and $x_1$ makes its decision based on $x_{k}$ and $x_2$.2011-01-21
  • 0
    I agree with Willie... without circular boundary conditions, the statement (precise or not) is clearly incorrect, because (whether $n$ and $k$ are large or not) you can have steady states in which each gap is one longer than the one to its left, e.g., stones at the triangular-numbered positions 1, 3, 6, 10, 15, 21, ...2011-01-21
  • 0
    @Willie Wong - I would be interested in the answer for the case of the circle as well.2011-01-21
  • 0
    @mjqxxx - I would actually consider positions such as $1,3,6,10, \ldots$ "approximately equispaced" because I'm really interested in what happens when $k$ is fixed and $n$ goes to infinity, in which case the extra pebble in the interval lengths makes no difference. But if this sounds artificial to you, I would be interested in the answer for the case of the circle as well.2011-01-21

1 Answers 1