Abelian sandpile model

From Wikipedia, the free encyclopedia
  (Redirected from Bak-Tang-Wiesenfeld sandpile)
Jump to: navigation, search

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 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. These "avalanches" are an example of the Eden growth model.

The model has since been studied on the infinite lattice, on other (non-square) lattices, and on arbitrary graphs.

Definition[edit]

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

Begin with some nonnegative configuration z(x,y) which is finite, in the sense that

\sum_{x,y}z(x,y)<\infty.

Any site 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 graph with a sink, 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.

Self-organized criticality[edit]

The original interest behind the model stemmed from the fact that 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.[2]

Cultural references[edit]

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[edit]

  1. ^ Bak, P., Tang, C. and 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. 
  2. ^ Moghimi-Araghi (2004). "Abelian Sandpile Model: a Conformal Field Theory Point of View". arXiv:cond-mat/0410434 [cond-mat].

Further reading[edit]

  • Per Bak (1996). How Nature Works: The Science of Self-Organized Criticality. New York: Copernicus. ISBN 0-387-94791-4. 
  • Perkinson, David; Perlman, Jacob; Wilmes, John (2013). "Algebraic geometry of sandpiles". In Amini, Omid; Baker, Matthew; Faber, Xander. Tropical and non-Archimedean geometry. Bellairs workshop in number theory, tropical and non-Archimedean geometry, Bellairs Research Institute, Holetown, Barbados, USA, May 6–13, 2011. Contemporary Mathematics 605. Providence, RI: American Mathematical Society. pp. 211–256. doi:10.1090/conm/605/12117. ISBN 978-1-4704-1021-6. Zbl 1281.14002.