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.

  • $\begingroup$ 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$. $\endgroup$ – Willie Wong Jan 21 '11 at 16:55
  • $\begingroup$ 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, ... $\endgroup$ – mjqxxxx Jan 21 '11 at 17:17
  • $\begingroup$ @Willie Wong - I would be interested in the answer for the case of the circle as well. $\endgroup$ – angela o. Jan 21 '11 at 17:41
  • $\begingroup$ @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. $\endgroup$ – angela o. Jan 21 '11 at 17:44

First some thoughts and not an answer. It is helpful to re-think the problem in terms of the gaps between the stones. You have $n$ slots with $k$ stones. So in the case with boundaries you have $(k+1)$ stretches of "in between space", each of which we will denote $a_i = x_i - x_{i-1} - 1$. The sum of all these $a_i$ add up to $n-k$. The dynamical system in terms of $a_i$ can be written as follows: let $a_0 = a_1$ and $a_{k+2} = a_{k+1}$ (translating the Dirichlet conditions of your original system to a Neumann boundary condition), and demand

$$ a_i(t+1) - a_i(t) = \lfloor \frac{a_{i+1}(t) - a_i(t)}{2}\rfloor - \lfloor \frac{a_i(t) - a_{i-1}(t)}{2}\rfloor $$

which is in fact (more-or-less) a discrete heat equation for $a:\mathbb{Z}\to\mathbb{Z}$. (The discrete Laplacian may also be written as $\lfloor (a_{i+1} + a_{i-1})/2\rfloor - a_i$ which differs from the RHS about by at most 1. The version above has instead the nice property that it preserves the $\ell_1$ norm of $a$, that is, the sum of all $a_i$ is preserved under this evolution.)

So we can apply similar intuition behind the heat equation: namely that one can expect convergence of the solution to a harmonic function. (The discretized setting however suggests that the limiting solution will not necessarily have $a_i(t+1) = a_i(t)$, but small fluctuations like $|a_i(t+1) - a_i(t)| \leq 1$ should be expected.)

Now, the harmonic functions on an intervale are the constant functions and the linear functions. The latter is ruled-out by the Neumann boundary condition. However, because of your discretization and the preferential placement of the stones to the left spot when two are equal, the modified Laplacian given above admits a harmonic function as described by mjqxxxx in his comment: since differences of +1 between consequentive $a_i$s are treated as if they don't exist. So you can have solutions which locally looks like it is equidistributed (left side and right side differs by a small amount) but globally isn't.

The periodic model, however, doesn't necessarily help. Consider the case with 4 stones and 12 slots. Take the initial distribution (O for stone, u for empty slot)


this becomes


and the pattern oscillates, never settling down. This example can be generalized to large $n$ also. This oscillation represents a failure of the intuition for passing from the continuous heat equation to the discrete case. When the spatial wavelength of the oscillation is small enough (on the order of the lattice size), artefacts from the discretisation starts to interfere with the intuition. We will see below that this artefact can only manifest for when there are even number of stones in the periodic case, can cannot manifest in the interval case.

Now more concrete answers. Using the property of the heat equation, one can be inspired to check for dissipation laws (in other words, apply the maximum principle for parabolic differential equations). And indeed, by the definition of the system, in either the interval case or the periodic case, you can easily check that

  1. The value $a_{min} = \min a_i$ is non-decreasing, and $a_{max} = \max a_i$ is non-increasing.
  2. Suppose $a_i$ attains the minimum at time $t$. Then $a_i(t+1) = a_i(t)$ if and only if $a_{i-1}(t) = a_i(t)$ and either $a_{i+1}(t) = a_i(t)$ or $a_{i+1}(t) = a_i(t) + 1$. Similarly for the maximum.

Reasoning directly from point 2 you obtain that, in the interval case (your original question), any distribution will converge toward a distribution that looks like the following: there exists $k_m$ and $k_M$ such that for all $i \leq k_m$, you have $a_i = a_{min}$. For all $i \geq k_M$, you have $a_i = a_{max}$. In between $k_m$ and $k_M$, you have $a_{i+1} - a_i = 1$. The values $k_m$ and $k_M$ can be $0$ or $k+1$, reflecting a limiting distribution that is a constant.


Let us re-write the discrete heat equation. A bit of computation shows that we can write it in the following way:

$$ a_i(t+1) = \lfloor \frac{a_{i+1}(t) + a_{i-1}(t) + \left( a_{i-1}(t) - a_i(t) \mod 2\right)}{2}\rfloor$$

which says that the value of $a_i$ at $t+1$ is the average of its neighbors at $t$, rounded up if $a_{i-1}-a_i$ is odd, and rounded down if it is even. So in the periodic case with $k$ even, there are even number of $a_i$s, which can be then partitioned into two (effectively non-interacting) subsets (the evens and the odds) that results in the oscillating behaviour noted above. In the case of the interval by the Neumann boundary condition, and in the periodic case with the odd number of stones, there cannot by such partition of the system into two independent subsystems.

(to be cont.)

  • $\begingroup$ thanks a lot for your answer! I am still processing it. A quick question: how do you obtain the conclusion (say for the interval case) from points 1 and 2? Suppose, for example, that $(a_0,a_1,a_2)=(1,20, -10)$. It seems like neither point 1 nor point 2 rules out the possibility that at the next time step we get $(a_0,a_1,a_2)=(-10,20,1)$, and at the following time step its back to $(1,20,-10)$. I am not questioning the conclusion, just wondering if something beyond points 1 and 2 is required. $\endgroup$ – angela o. Jan 21 '11 at 21:28
  • $\begingroup$ You are right. I've omitted some things. I'll fill them in tomorrow. $\endgroup$ – Willie Wong Jan 22 '11 at 0:52
  • $\begingroup$ But OOuuuuOOuuuu goes to OuuOOuuuuOuu, not uuuOOuuuuOOu. Are you saying that it becomes uuuOOuuuuOOu after some number of steps $\endgroup$ – TonyK Jan 22 '11 at 7:45
  • $\begingroup$ @TonyK: read it again, I was talking about the periodic modification to the original problem with NO boundaries. The left and right hand sides wrap around the same way in, say, PacMan. So for the first stone on the left, it sees four spaces to its left and 0 spaces to its right, or that it sees a total of 5 spaces (including the one it currently occupies) between its nearest neighbours. $\endgroup$ – Willie Wong Jan 22 '11 at 13:46
  • $\begingroup$ @angela: after thinking about it a bit more, the question is actually a bit tougher than I thought. The existence of the oscillating solution in the even periodic case implies that it is crucial to factor in the global structure of the lattice. (In the interval case, make use of the boundary layer dynamics to rule out periodic orbits; in the odd periodic case, using parity to rule out oscillations.) I do not immediately see how. I'll think about it more, but I'm not sure if my approach is completely valid. $\endgroup$ – Willie Wong Jan 22 '11 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.