Chip firing

Everybody has some number of coins. Every clock tick everybody gives one coin to each of his neighbours, provided he has sufficient coins to do so.

This 0-person game is played on a graph (so that "neighbour" is defined). It is known under various names, like "chip firing" and "sandpile".

Sinks

A sink is a node in the graph that only receives but never gives. (In the sandpile applet sinks are drawn black. In particular, the outer boundary consists of sinks. In the chipfire applet sinks are red.)

When sinks are present, every state will stabilize after finitely many steps: money disappears into the sinks until nobody has enough left to give one coin to each of his neighbours. (In the sandpile applet the "single step" button does one clock tick, the "go" button runs the time until the state has become stable.)

Recurrent states

Let Z be the state space: the set of all vectors with nonnegative integral entries, indexed by the nodes of the graph. Let S be the subset of Z consisting of all stable states. Then Z is infinite, but S is finite (assuming that the graph is finite).

We have an operation * on Z: given two vectors u and v in Z, let u*v be the vector obtained by first taking the state u+v and then letting that stabilize. The set S together with the operation * is a monoid.

A state u in S is called recurrent if u*z = u for some strictly positive vector z. Let R be the set of recurrent states in S. Then (R,*) is an abelian group.

For every z in Z there is a unique r in R such that u*z = u*r for all u in R. This r is called the reduction of z. In particular, the identity of the group R is the reduction of the zero vector. The elements of R are their own reduction, so that "reduced" and "recurrent" are synonymous. (In the sandpile applet, the "reduce" button computes the reduction of a given state.)

Exercises

Check with the sandpile applet that an all-red field is reduced. Why?

Check with the sandpile applet that doubling the identity and reducing gives the identity again. Why? Show that this property characterizes the identity.

Show that every finitely generated commutative semigroup carries a group on its recurrent elements (provided there are any). How should recurrent be defined here?

Problems

An avalanche is the set of nodes that is involved in the reduction of an arbitrary state to a stable one. Single point changes to a recurrent state can cause both small and large avalanches. Can something be said about the avalanche size?

Can something be said about the time needed to obtain a stable state?

The avalanche of a single point is simply connected. Why?