0README

percolation
|-- 0README                         obvious
|-- burn.gif                        12 summary images from xtoys "xburn"
|-- burn-data                       data from burn.gif: time + extent
|-- burn.s                          R commands: analysis of burn-data
|-- burn-output.ps                  plots generated by analysis
`-- perc.s                          R commands: fill a lattice randomly


PERCOLATION

Percolation theory and its application is a way to enter into the
subject of phase transitions.  The fundamental concepts of percolation
are perhaps more intuitive than those of the Ising and other models
of phase transitions. Yet pecolation displays the central properties
of a phase transition: correlation (cooperativity); nonlinearity
(explosive growth); emergence of a new structure (infinite
connectivity); power law behavior (universality).  The percolation
model applies variously to: the penetration of a gas into the
adsorbant matrix of a gas mask (the early application from which
the percoclation model derived its name); the conduction of current
across a thin metal film; the properties of partially hydrated
protein; the growth of a forest fire (or epidemic); the formation
of a galaxy; and much more. Tutorials on percolation theory are to
be found on the web.

Percolation theory in more than one dimension is mathematically
difficult but simple to demonstrate.  Two instances are considered
here:

	forest fires; 
	filling a square lattice randomly.



FOREST FIRES

We model a forest by a square lattice, wrapped edge to opposite
edge.  Some fraction, p, of the sites are randomly occupied by
trees.  A fire is started at all filled sites along one edge (along
a line with gaps in the wrapped surface).  The growth of the fire
is simulated in steps.  A step corresponds to an interval of time.
At each step the fire propagates with unit probability to a neighboring
site if it has a tree.

Clearly, if only a small fraction of the sites have a tree, the
fire will die out quickly, burning only a few trees near the edge,
and without burning a large fraction of the tree-ed sites.  At high
tree density (initial fraction filled large, p ~ 1), the fire will
spread quickly and essentially all trees will burn.  At some
intermediate density, the fire will reach all regions of the forest
(the burn will touch all edges of the forest) but the burn is slow.
This intermediate density, at which the fire can reach all regions
of the forest, is the critical density, p-c, at which there is an
infinite cluster of trees.  Percolation theory tells us that for a
square lattice, p-c = 0.59.  The network of trees at p-c is wispy
(fractal).  Thus the path through it is long and tortuous and the
burn is slow.  For p < p-c, the burn paths are shorter; also for p
> p-c, the burn paths become shorter as the strength of the infinite
cluster, P(p), increases. (P(p) = probability a site is part of the
infinite cluster; P(p) is the order parameter for the percolation
model.)

A simulation of the above model, xburn, is one of the original
"xtoys" by Mike Creutz of BNL (xburn is not in the current xtoys
package).  The code and instructions for xburn are in the directory
/Users/jar/Sites/Rupley/Code/xtoys.

Twelve images from simulations for p=.2-.9 are shown in the file
"burn.gif".  Each image gives the time for the burn (as the number
of iterations) and the number of trees left unburnt.

These data (in the file "burn.data") are shown in the two plots of
the file "burn-output.ps", for the fraction unburnt and the time
of the burn versus the fraction filled, p.  The file "burn.s" has
the R language commands to generate the plots.

Note that as expected from theory, the percolation transition is
near p=0.59 and the time of the burn is maximum at the transition.

The model for a forest fire applies also to epidemics.  For a disease
to burn through a population, not only must it be highly contagious,
but the density of susceptible individuals must be high.  A disease
like aids may, as in Western countries, affect a sub-population,
but not the entire population.



FILLING A SQUARE LATTICE RANDOMLY


A Simple Demonstration of Percolation

[This is written (and was given) as a student exercise.]

[The R language commands in perc.s allow one to generate the set of
random numbers and to observe the filling of the lattice on a
computer screen.]

Carry out a simulation of site percolation on a 10 x 10 square
(two-dimensional) lattice.  The minimum you need for doing this is
a source of random numbers, to generate a list of the order in which
the sites are filled.  Tables of random numbers are available, and
most computers have software for generating a set of acceptably
random numbers.  You may want to write a small program to generate
the list of the order of filling.

It is probably easiest to track the behavior of the system by hand,
using a 10x10 grid drawn on paper and filling the sites one-by-one,
following the previously-generated list of random filling order.

Record the point of appearance of the infinite cluster, here defined
as a cluster that connects (touches) all *four* edges of the lattice.
This defines for your simulation the percolation threshold, p-c,
the fraction of sites filled at the appearance of the infinite
cluster.  Note that for a square lattice, each site has only four
neighbors: up, down, left and right.  [Diagonal neighbors do not
count when determining clusters and paths through the lattice.]


Response Requested:

(a) Briefly explain how you carried out the simulation.  If you
wrote a computer program, please submit it.

(b) Show your partially filled lattice at p-c.

(c) Compare your value of the threshold, p-c, with the literature
value, and comment.

(d) Turn in a plot of P(p) as a function of the fraction of sites
filled.  To do this, as you fill  each site above the threshold
(transition) at p-c, record the number of filled sites that are
part of the infinite cluster, as a function of the number of sites
filled.  From this information, calculate the percolation probability,
P(p), as a function of the fraction of sites filled.  (NOTE: P(p)
is the number of filled sites that are part of the infinite cluster
divided by the total number of sites of the lattice (filled and
unfilled).  P(p) is the order parameter and is also known as the
strength of the infinite cluster.)

(e) Submit a plot of log (P(p)) vs log (p - p sub c ).

(f) Determine the critical exponent, beta, from the above plot.
Compare your value with the literature value, beta=.14, and comment.

----------------------------------------------------------------------
----------------------------------------------------------------------

Class average values(for 11 students): pc = .605 (theory, .59);
beta = .180 (theory, .14).  The average for pc should be close to
theory, as it is.  The average for beta is close but not as
convincingly.  The exponent should be determined from data near pc;
this is not possible for a small lattice, owing to the jump character
of P(p) for a small lattice (insufficiently smooth to determine
slope well near pc).  Thus for the class data, the values of beta
jump a lot, like the P(p) plot.

This problem was assigned because there appeared to be uncertainty among
the class as to the nature of a percolation phase transition and the power
law behavior of the order parameter.  


John Rupley
 rupley@u.arizona.edu -or- jar@rupley.com
 30 Calle Belleza, Tucson AZ 85716 - (520) 325-4533; fax - (520) 325-4991
 Dept. Biochemistry & Molecular Biophysics, Univ. Arizona, Tucson AZ 85721
