theory.txt

模拟2维沙堆效果

To describe the principles in a sandpile there is a certain model that is 
useful. This is the cellular automaton model, introduced by von 
Neumann.

A cellular automaton represents a closed system where the elements 
of the system (called cells) are organized in a structure (a 2-
dimensional matrix, for example). The cells are represented as 
variables (or groups of variables) with discrete values. The state of 
the cellular automaton is determined entirely from the values in each 
cell.

The system is dynamic (it develops over time). The values of each 
cell are updated depending on two factors: 1) the local environment 
(the values in each of the neighboring cells in the previous time unit), 
and 2) a local set of rules. All cells in the automaton are updated 
simultaneously.

A lot of systems in real life can be modelled by the cellular automaton 
model. In physics especially, there are many problems that contain 
many discrete elements with local interactions (eg. the molecules in a 
crystal). There even exists parallel computer architectures based on 
these principles.

You may already know Conway's "Game of Life", which is an 
excellent example of a simple cellular automaton (and at the same 
time a SOC system). In this game each cell in a grid arranges itself 
based on how its eight neighbor cells are arranged. The system 
interacts with itself, but in time it finds a critical state from which 
it won't change unless the cells are changed from outside the system.

Our sandpile is modelled as a cellular automaton. The model is dynamic, 
and the dynamics is based on two factors: 1) the environment (neighbor 
cells), and 2) a local set of rules, which in this case is the same in 
the whole system (all cells). Also, all grains (cells) are updated 
simultaneously (in the same round). So, as you can see, the underlying 
principles for our sandpile model and the "Game of Life" are exactly the 
same.

3. RESULTS OF THE SIMULATION

It is possible to create a number of rules and formulas for the 
behaviour and attributes of a sandpile model, but I will mention just 
one, which is chained to the execution time of the simulation.

The size of an avalanche, s, can vary significantly over time, but the 
distribution of the avalanche sizes can be expected to follow a 
power law (except probably when the sandpile is modelled with the 
Laplacian approach). In other words: s increases with a power 
exponent relative to the number of acumulated grains. Which, in 
english, means: the more grains you add, the bigger the avalanches 
will get - on average. This is hardly surprising.

The formula for the distribution of s is: D(s) ~ s^(1-t), where t 
represents an exponent of size (?), which you can estimate. The size 
of t will depend on the rules of the sandpile model you construct.

Among the factors which influence the dynamics of the sandpile are: 
the size of the pile, its initial state, the rules which determine when 
to topple, and the size of the introduced pertubation (the number of 
grains added at any one time).

One of our goals with our program was to verify that the simulation 
follows a power law in execution time and the size of the avalanches. 
By running a number of simulations and using the above-mentioned 
formula, we estimated t to be approx. 1.491. We did this by letting 
the program generate test-results during the simulations (containing 
the size of avalanches relative to the total number of grains). The 
results were processed in the Excel spreadsheet.

If you like, you can see if you get the same result (you ought to, 
unless I unintentionally changed the program after we ran the 
simulations). The source code of the program includes a tailored log 
object, which has been disabled for purposes of speed. You only 
need to un-comment the object in the main simulation loop (see file 
sandsim.pas).

By the way, the formula is only valid, as long as the surface area is 
big enough to hold all sand grains. When they begin falling over the 
edges, D(s) will be more linear over time, as the lost grains cannot 
start or be part of a chain reaction.

4. CONCLUSION

The SOC theory provides rules for how large, complex, interacting 
systems over time organize themselves around one or more critical 
factors in the system. Our sandpile model was a simple example of 
that.

In real life there are many examples of these large, complex, 
interacting systems - like the stock market, eco-systems, traffic, or 
the weather. Systems like these are quite robust, but every now and 
then they can collapse with just a little outside influence (a bit scary, 
huh?). Keep in mind, though, that systems like these are not closed 
systems, unlike the sandpile model. It is possible to adjust the 
systems somewhat from outside to prevent them from collapsing (the 
opposite is also possible).

Somewhere, I once read a suggestion to why the dinosaurs grew 
extinct. The suggestion involved elements of SOC theory, and I guess 
it went something like this: The entire dino population (or the eco-
system) had organized itself around some unknown factors (maybe 
the relationship between herbivores and carnivores, or other 
"demographic" factors), so the dino population depended on these 
factors. Some outside condition, which might have been insignificant, 
had the system been in another state, was introduced, and WHAMMO! 
The system avalanched itself into destruction. So it didn't have to be 
a doomsday meteorite - it could have been just a bad case of the dino 
flu. Over millions of years the system had worked itself into a critical 
state from where it could virtually destroy itself without much effort.

You see it all the time in nature: if the eco-system is disturbed 
somewhere, the whole system feels the effects. Like avalanches in a 
sandpile, these effects can be of varying size. Eventually, a new 
balance will be established in the eco-system. That just didn't happen 
in the case of the dinos. 

Personally, I kind of like this suggestion. It has some implications that 
make you think.

This concludes what I want to say about sandpiles. Perhaps you find 
sandpiles and SOC systems to be fascinating, perhaps not. If you 
want to go further, I've included a few references that might be useful 
(be aware that most of them are pretty technical - and probably a bit old 
by now). Also, try searching the Internet using keywords like "self-
organized criticality" and "complex [adaptive] systems" - there抯 loads 
of stuff out there.

Any comments, questions, suggestions, corrections, or the like are 
very welcome.


Troels Jakobsen
[e-mail]



References

1. Per Bak + Kan Chen: "Self-Organized Criticality", Scientific 
American, Jan 1991. (This is a good article on SOC - interesting 
and relatively easy)
 
2. Per Bak + Kan Chen + Michael Creutz: "Self-Organized 
Criticality in the 'Game of Life'", Nature, vol 342, Dec 14 
1989. (More about cellular automatons, the Game of Life, and 
sandpiles - a short and rather technical article)
 
3. Per Bak + Chao Tang + Kurt Wiesenfeld: "Self-Organized 
Criticality: An Explanation of 1/f Noise", Physical Review 
Letters, vol 59:4, July 27 1987. (A rather technical article of a 
SOC phenomenon known as flicker noise)
 
4. Per Bak + Chao Tang + Kurt Wiesenfeld: "Self-Organized 
Criticality", The American Physical Society, vol 38:1, July 1 
1988. (More about flicker noise in 1-, 2-, and 3-dimensional 
sandpile models - technical but thorough)
 
5. Steven A. Janowsky + Claude A. Laberge: "Exact solutions for 
a mean-field Abelian Sandpile", Working papers - Rutgers 
University, June 1993. (Found somewhere on the Internet)
 
6. Yu Feng + Heather J. Ruskin: "Large scale Simulation and 
Applications", Working papers - Dublin University, June 1994. 
(Found somewhere on the Internet)
 
7. V. B. Priezzhev + D. V. Ktitarev + E. V. Ivashkevich: 
"Formation of Avalanches and Critical exponents in Abelian 
Sandpile Model", Working paper - Joint Institute of Nuclear 
Research, 1980 (?). (Found somewhere on the Internet)