The Amazing, Autotuning Sandpile | Hacker News Reader

The Amazing, Autotuning Sandpile

nautil.us

26 pointsdnetesn5 comments

Both the article and Wikipedia mention two facts:

(1) The process is guaranteed to terminate given that the initial configuration was finite.

(2) Moreover, although there will often be many possible choices for the order in which to topple vertices, the final configuration does not depend on the chosen order.

Are there proofs of these facts, or are they just assertions based on numerical experiments?

I can give you a proof for (1). Use manhattan distance. Take an arbitrary point P. Sand can not get arbitrarily far from P.[0] Thus there is a highest distance n from P sand can reach. Whenever sand collapses, at least one grain gets further from P. Thus there are no collapses at distance n. There are a finite number of points at distance n, so there are a finite number of collapses at n-1. But that means a finite number of grains enter n-1, so finite number of collapses at n-2. And so on.

[0] Consider the path that the sand would travel to get super far out. The path cannot contain any adjacent empty cells (proved in the article). Thus it would take infinite sand to get infinitely far out.

Yes, these are theorems! I don't think they're too hard, either, though it's been a while since I've thought about this sort of thing, and maybe there's some reason they're harder than I expect. (You'll probably want to look up the diamond lemma for the second.)

The Wikipedia article is surprisingly bare. There's a lot more known about sandpiles than that. So, this seems to be an appropriate time to infodump on some basics. :)

For instance, you can consider sandpiles on finite graphs (a vertex topples when the number of grains on it is at least its degree). Of course, this will never terminate by itself, but if we designate beforehand one of the vertices as a sink, then (assuming the graph is connected) it will.

We can then ask which configurations are reachable (by adding sand anywhere) from any other configuration. (For instance, the configuration where all vertices are just about to topple is necessarily reachable from any other configuration, by just adding the appropriate amount of sand to each vertex). This is often phrased in terms of Markov chains -- we consider a random process where you choose randomly which vertex to add sand at, and these are the recurrent states of this process.

Then in fact the number of such recurrent states doesn't depend on the chosen sink, and is equal to the number of spanning trees of the graph.

Not only that, you can actually make the recurrent states into a (commutative) group -- the group operation is to just add up two states vertex by vertex, and then topple to get the result. Note that the identity in this group is not the all-zero state, because that isn't recurrent! (Well, unless your graph is a star graph and you chose the center to be the sink.) Again, which vertex you pick as the sink doesn't matter; the groups you get this way are all isomorphic. They can also be defined more intrinsically, without picking a sink; look up the "Jacobian group" or "Picard group" of a graph.

Sandpiles are also studied under the name "chip-firing games". Another term to search on. There unfortunately seems to be a proliferation of names for the same thing in this field...

I am in a problem solving mood. Termination can be proved for finite graph with sink as: For every grain, compute its distance to the sink along the shortest route. For grains that entered the sink, use 0. Sort the values and put them in a vector. Note that there are finitely many possible vectors for a given number of grains and a given graph. Compare vectors lexicographically. With every topple at least one grain comes closer to the sink. This means that the vector decreases for every topple.

Ooh, that's more elegant than the direction I was going with (which I'm not sure would have worked). Note that the "sort, put in vector, order lexicographically" can be rephrased as "keep a vector of how many grains are at each distance, compare lexicographically". I think that makes it a little clearer.

Reply on news.ycombinator.com