Abelian sandpile model

The Abelian sandpile model, also known as the Bak–Tang–Wiesenfeld model, was the first discovered example of a dynamical system displaying self-organized criticality. It was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper.^[1]

28 million grains dropped.

The model is a cellular automaton. In its original formulation, each site on a finite grid has an associated value that corresponds to the slope of the pile. This slope builds up as "grains of sand" (or "chips") are randomly placed onto the pile, until the slope exceeds a specific threshold value at which time that site collapses transferring sand into the adjacent sites, increasing their slope. Bak, Tang, and Wiesenfeld considered process of successive random placement of sand grains on the grid; each such placement of sand at a particular site may have no effect, or it may cause a cascading reaction that will affect many sites.

The model has since been studied on the infinite lattice, on other (non-square) lattices, and on arbitrary graphs (including directed multigraphs).^[2]

Definition

The iteration rules for the model on the square lattice can be defined as follows:

Begin with some nonnegative configuration $z(x,y)\in {\mathbf {Z}}$ which is finite, in the sense that

\sum _{{x,y}}z(x,y)<\infty

Any site $(x,y)$ with

z(x,y)\geq 4

is unstable and can topple, sending one of its chips to each of its 4 neighbors:

z(x,y)\rightarrow z(x,y)-4

z(x\pm 1,y)\rightarrow z(x\pm 1,y)+1

z(x,y\pm 1)\rightarrow z(x,y\pm 1)+1.

The process is guaranteed to terminate given that the initial configuration was finite. 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; this is one sense in which the sandpile is Abelian. The number of times each vertex topples in this process is also independent of the choice of toppling order.

On an arbitrary undirected graph, a special vertex called a sink is specified that is not allowed to topple. In the presence of a sink, the term chip configuration refers to a chip-counting vector (nonnegative and integral) indexed by the non-sink vertices. The rules are that any non-sink vertex $v$ with

z(v)\geq {\mathrm {deg}}(v)

is unstable; toppling again sends one of its chips to each of its neighbors:

z(v)\rightarrow z(v)-{\mathrm {deg}}(v)

and, for each $u\sim v$ :

z(u)\rightarrow z(u)+1.

Multiple toppling operations can be efficiently encoded by using the Laplacian matrix $\Delta$ . Deleting the row and column of $\Delta$ corresponding with the sink yields the reduced Laplacian $\Delta '$ . If $\mathbf {x}$ is a nonnegative integral vector indexed by the non-sink vertices, then starting with a configuration $z$ and toppling each vertex $v$ a total of ${\mathbf {x}}(v)$ times yields the configuration $z-{\mathbf {x}}\Delta '$ .

This and other models that involve a toppling operation are sometimes referred to as chip-firing models or chip-firing games.

Sandpile group

Given a configuration $z$ , toppling unstable non-sink vertices on a finite connected graph until no unstable non-sink vertex remains leads to a unique stable configuration $z^{{\circ }}$ , which is called the stabilization of $z$ .

The set of stable configurations forms a commutative monoid under the operation $z*w\to (z+w)^{{\circ }}$ . The minimal ideal of this monoid is a group of recurrent configurations called the sandpile group. A stable configuration is recurrent if it can be gotten from any other configuration by adding chips and stabilizing.

The sandpile group is isomorphic to the group of equivalence classes of configurations gotten by reducing modulo the toppling operation, which can be written

{\mathbf {Z}}^{{n-1}}/{\mathbf {Z}}^{{n-1}}\Delta '

where $n$ is the number of vertices and ${\mathbf {Z}}^{{n-1}}\Delta '$ is the integer row-span of $\Delta '$ .

The order of the sandpile group is the determinant of $\Delta '$ , which by the matrix tree theorem is the number of spanning trees of the graph.

Self-organized criticality

Main article: Self-organized criticality

The original interest behind the model stemmed from the fact that in simulations on lattices, it is attracted to its critical state, at which point the correlation length of the system and the correlation time of the system go to infinity, without any fine tuning of a system parameter. This contrasts with earlier examples of critical phenomena, such as the phase transitions between solid and liquid, or liquid and gas, where the critical point can only be reached by precise tuning (e.g., of temperature). Hence, in the sandpile model we can say that the criticality is self-organized.

Once the sandpile model reaches its critical state there is no correlation between the system's response to a perturbation and the details of a perturbation. Generally this means that dropping another grain of sand onto the pile may cause nothing to happen, or it may cause the entire pile to collapse in a massive slide. The model also displays 1/ƒ noise, a feature common to many complex systems in nature.

This model only displays critical behaviour in two or more dimensions. The sandpile model can be expressed in 1D; however, instead of evolving to its critical state, the 1D sandpile model instead reaches a minimally stable state where every lattice site goes toward the critical slope.

For 2 dimensions, the associated conformal field theory is suggested to be symplectic fermions with central charge c=-2.^[3]

Generalization to directed graphs

The sandpile model can be generalized to arbitrary directed multigraphs. The rules are that any vertex $v$ with

z(v)\geq {\mathrm {deg}}^{{+}}(v)

is unstable; toppling again sends chips to each of its neighbors, one along each outgoing edge:

z(v)\rightarrow z(v)-{\mathrm {deg}}^{{+}}(v)+{\mathrm {deg}}(v,v)

and, for each $u\neq v$ :

z(u)\rightarrow z(u)+{\mathrm {deg}}(v,u)

where ${\mathrm {deg}}(v,u)$ is the number of edges from $v$ to $u$ .

In this case the Laplacian matrix is not symmetric. If we specify a sink $s$ such that there is a path from every other vertex to $s$ , then the stabilization operation on finite graphs is well-defined and the sandpile group can be written

{\mathbf {Z}}^{{n-1}}/{\mathbf {Z}}^{{n-1}}\Delta '

as before.

The order of the sandpile group is again the determinant of $\Delta '$ , which by the general version of the matrix tree theorem is the number of oriented spanning trees rooted at the sink.

Least action principle

The stabilization of chip configurations obeys a form of least action principle: each vertex topples no more than necessary in the course of the stabilization.^[4] This can be formalized as follows. Call a sequence of topples legal if it only topples unstable vertices, and stabilizing if it results in a stable configuration. The standard way of stabilizing the sandpile is to find a maximal legal sequence; i.e., by toppling so long as it is possible. Such a sequence is obviously stabilizing, and the Abelian property of the sandpile is that all such sequences are equivalent up to permutation of the toppling order; that is, for any vertex $v$ , the number of times $v$ topples is the same in all legal stabilizing sequences. According to the least action principle, a minimal stabilizing sequence is also equivalent up to permutation of the toppling order to a legal (and still stabilizing) sequence. In particular, the configuration resulting from a minimal stabilizing sequence is the same as results from a maximal legal sequence.

More formally, if $\mathbf {u}$ is a vector such that ${\mathbf {u}}(v)$ is the number of times the vertex $v$ topples during the stabilization (via the toppling of unstable vertices) of a chip configuration $z$ , and $\mathbf {n}$ is an integral vector (not necessarily non-negative) such that $z-{\mathbf {n}}\Delta '$ is stable, then ${\mathbf {u}}(v)\leq {\mathbf {n}}(v)$ for all vertices $v$ .

Cultural references

The Bak–Tang–Wiesenfeld sandpile was mentioned on the Numb3rs episode "Rampage," as mathematician Charlie Eppes explains to his colleagues a solution to a criminal investigation.

The computer game Hexplode is based around the Abelian sandpile model on a finite hexagonal grid where instead of random grain placement, grains are placed by players.

References

↑ Bak, P.; Tang, C.; Wiesenfeld, K. (1987). "Self-organized criticality: an explanation of 1/ƒ noise". Physical Review Letters. 59 (4): 381–384. Bibcode:1987PhRvL..59..381B. doi:10.1103/PhysRevLett.59.381.
↑ Holroyd, A.; Levine, L.; Mészáros, K.; Peres, Y.; Propp, J.; Wilson, B. (2008). "Chip-Firing and Rotor-Routing on Directed Graphs". In and Out of Equilibrium 2. 60: 331–364. Bibcode:1987PhRvL..59..381B. doi:10.1007/978-3-7643-8786-0_17.
↑ Moghimi-Araghi (2004). "Abelian Sandpile Model: a Conformal Field Theory Point of View". arXiv:cond-mat/0410434 [cond-mat].
↑ Fey, A.; Levine, L.P; eres, Y. (2010). "Growth Rates and Explosions in Sandpiles". Journal of Statistical Physics. Springer US. 138 (1-3): 143–159. arXiv:0901.3805. Bibcode:2010JSP...138..143F. doi:10.1007/s10955-009-9899-6. ISSN 0022-4715.

Sandpile model on arxiv.org