The Percolation Problem
by Michael Cohen
Takoma Park Middle School
Table of Contents
Introduction .................................................................................................. 2
Experiment Design........................................................................................ 3
Procedure...................................................................................................... 4
Results........................................................................................................... 5
Appendix........................................................................................................ 8
Bibliography.................................................................................................. 10
Glossary......................................................................................................... 10
The study looked at the specific problem of site percolation on a square lattice (grid). This problem can be explained in the following way. Imagine an infinite apple orchard, which is arranged in a square lattice. Imagine a disease to which some trees (sites) are resistant, with probability p that a tree is susceptible (occupied). This disease has the characteristic that it will spread from a tree to all adjacent susceptible trees, and if a susceptible tree is exposed, it will get the disease. If one tree is exposed to the disease, a whole group (cluster) may be infected. How far will the disease spread? The cluster size is defined as the number of infected trees. A cluster is said to percolate when the cluster has infinite size. The percolation threshold is the value of p such that all higher values of p will have some percolating clusters.
There are many other percolation problems. There are other lattices, some of them 3-dimensional. Also, there is a type of percolation problem called bond percolation. A bond percolation problem on a square lattice can be thought of in this way. Imagine you have a perfect grid of streets, after a snowstorm. An "occupied" street, or bond, is drivable. How many streets can you drive to? A cluster in this problem is a group of all the streets you can drive to, and the cluster size is defined as the number of accessible streets. "Percolate" and "percolation threshold" have the same meaning as before. One application of these problems in the real world is the diffusion of a fluid through a porous solid. One way to interpret this is to use a three-dimensional lattice and have sites that are occupied be holes and unoccupied site be filled up. Once this has been done, it is a simple site percolation problem. Fluids will begin to diffuse through the entire solid at values of p at about the percolation threshold ("about") because real-world lattices are finite).
 |
To give a sense of what a typical
cluster looks like, a typical site cluster on a square lattice at p=0.573
is shown below. This cluster is finite (not percolated), and shows that clusters
have a somewhat fractal-like quality, though the finite clusters such as this
one are not technically fractals. This cluster is large because p is
close to the percolation threshold.
Many very good approximations have been done for percolation problems. They utilized more computer power than was available for this project. Below is a table of some of the best approximations of percolation thresholds for a few percolation problems, researched prior to the experiment.
Approximate Percolation Thresholds
|
Lattice |
Site Percolation Threshold |
Bond Percolation Threshold |
|
Square |
0.59275 |
0.5 |
|
Triangular |
0.5 |
0.34729 |
|
Simple Cubic (3-Dimensional) |
0.3117 |
0.2492 |
Notice that the bond percolation thresholds for the triangular and simple cubic lattices are noticeably smaller than the site percolation thresholds. This is due to the fact that a bond has more adjacent bonds than a site has adjacent sites. The more adjacent sites or bonds available, the more likely a given occupied site or bond will have at least one occupied neighbor, causing spreading. In three dimensions, there are also more adjacent sites and bonds than in two dimensions, which lowers the percolation threshold for the same reason. In the one-dimensional case, bond percolation is identical to site percolation, because each is connected to its neighbors in the same way. In either case, all sites or bonds must be occupied for percolation to occur. Therefore, the percolation threshold for a line lattice is 1.
The study calculates an approximation of the mean cluster size (over multiple trials). It is not exact since there is no known method to compute the mean cluster size exactly. This "experiment" is actually a computer simulation designed by the author of this work, with an algorithm he developed.
The percolation threshold can be derived from the mean cluster size. When does the size get to infinity? At the threshold. The approximation of the threshold from this study is within about one percent of the best estimate done so far. The reason it is not much closer is the size of the lattice, which was limited by resources. The lattice had approximately nine million sites. Percolation was approximated by the cluster extending to the edge of the lattice, having started in the middle. However large the lattice may seem, it is not large enough to get as accurate values of the percolation threshold as are currently known. This effect can be seen in the cluster below, on a 201 ´ 201 lattice with p=0.575.
 |
Note that this cluster is below the percolation threshold by a relatively large amount, but it still extends to the edge of the lattice. This means that if a lattice this small was used for calculations, the approximate percolation threshold would be lower than 0.575.
The independent variable was the value of p. The hypothesis was that the mean cluster size would increase rapidly as the value of p went to around 0.6, and then go to "infinity". This is because in an exact case, it must go to infinity at the percolation threshold, which, as shown in the table earlier, is around 0.6. The only materials used were a personal computer and a free version of Borland C++.
The procedure is to randomly (technically pseudo-randomly) "grow" a cluster on a lattice. If the cluster extends to the edge of the lattice, it is defined as percolation. 10,000 trials are used for the base procedure for each value of p. To determine the accuracy, this is repeated 10 times for each p.
The clusters are grown many times using a C++ computer program based on a recursive algorithm. C++ is a computer programming language, and recursive means that a section of the code calls itself. The program uses a 3001 ´ 3001 lattice, and 10,000 trials, as stated earlier.
The algorithm is as follows. Start with an empty square 3001 ´ 3001 lattice, and a variable we will call "overall cluster size" set to zero. Perform the "Process" at the site (1500, 1500), near the center of the lattice. Repeat that 9,999 more times, without resetting the "overall cluster size". The "overall cluster size" will then be the sum of all 10,000 trials' cluster sizes. Divide by 10,000 to get the mean.
Process (ordered pair (X, Y) as input):
Check if the site at the inputted position has been previously visited. If it has, stop. If not, check if it is within the 3001 ´ 3001 lattice. If not, stop all copies of the "Process," skip all future trials, and give the result "Probably percolated." If it is in the lattice, randomly decide, based on p, whether or not the site is occupied. If it is not occupied, stop. If it is, increase the "overall cluster size" variable by one and perform the "Process" with the following ordered pairs: (X + 1, Y), (X - 1, Y), (X, Y + 1), and (X, Y - 1), the neighboring sites.
If you analyze exactly what this does, you will see that it does in fact grow random clusters and report the mean result. It is far easier to generate this algorithm from the basic idea of site percolation than it is to extract the basic idea from the algorithm.
The cluster size did increase extremely rapidly with the increase of p, as was my hypothesis. With this system, the approximate percolation threshold was between 0.58 and 0.585. This can also be seen by looking at the graphs; these suggest that the cluster size will go to infinity at about p=0.58 to p=0.6. This, however, is not extremely accurate, being slightly lower than the most accurate threshold approximations, around 0.59275. The reason for this is the finite size of the lattice. This means that some of the clusters identified as percolating turn out to be finite. As stated earlier, computer power to get significantly more accurate results was not available for this study. Below are two graphs, which together plot the data. Note that the lowest point on the second graph is the highest on the first. Also note that on the second graph the y-coordinate scale is 100 times larger, while the x-coordinate scale is smaller and starts on 0.5 instead of 0.
Graphs Showing the Relation Between p and the Mean Cluster Size
(Dots are the values of each run (10,000 trials), and lines connect the averages of 10 dot values for each value of p)
Table of p and Mean Cluster Size (3 significant figures)
|
p |
0.1 |
0.2 |
0.3 |
0.4 |
0.45 |
0.5 |
0.55 |
0.57 |
0.575 |
0.58 |
|
Mean cluster size (10 runs, 100,000 clusters) |
0.156 |
0.521 |
1.47 |
4.89 |
10.6 |
30.1 |
189 |
854 |
1510 |
3320 |
|
Minimum mean cluster size for run (10,000 clusters) |
0.152 |
0.511 |
1.42 |
4.71 |
10.2 |
29.0 |
184 |
815 |
1450 |
3210 |
|
Maximum mean clusters for run |
0.162 |
0.546 |
1.55 |
5.10 |
11.1 |
31.2 |
196 |
899 |
1570 |
3490 |
The difference between the minimum and maximum cluster sizes gives some estimate of the accuracy of the results. This is why 10 seperate runs are performed. The 10 individual runs differ in total by about 10%. More accurate studies could use more run and/or more trials per run.
 |
Below is a picture of a cluster that may
well be percolated. This is only a 201 by 201 lattice, so the picture
may not be very accurate. However, you can see that the cluster extends
to the border of the image.
(Written in C++ by the author of this work)
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
void ClusterBuilder(int, int);
// Sites that have already been visited
int useless[3001][3001];
// Probability that a site has a susceptable tree
double prob;
// Total cluster size for all tries
int clusterSize;
// Has it reached the edge?
bool percolated = false;
// What trial are we on?
int trial;
int main()
{
// Initialize the random number generator
srand(time(NULL));
cout << "What is the probability? ";
cin >> prob;
for(int j = 0; j <= 3000; j++)
{
for(int k = 0; k <= 3000; k++)
{
// Allow all sites to have resistant trees
useless[j][k] = 0;
}
}
for(int i = 1; i <= 10000 && !percolated; i++)
{
trial = i;
// Expose the middle tree
ClusterBuilder(1500, 1500);
}
if(!percolated) cout << double(clusterSize) / 10000 << flush;
else cout << "Probably percolated." << flush;
return 0;
}
// Infects trees and decides their susceptability
void ClusterBuilder(int x, int y)
{
// Has it reached the edge
if((x < 0 || x > 3000) || (y < 0 || y > 3000))
{
// It's reached the edge
percolated = true;
return;
}
if(rand() < prob * 32768 && !(useless[x][y] == trial))
{
// This tree has been infected
useless[x][y] = trial;
clusterSize++;
ClusterBuilder(x + 1, y);
ClusterBuilder(x - 1, y);
ClusterBuilder(x, y + 1);
ClusterBuilder(x, y - 1);
}
// This tree has been previously visited
useless[x][y] = trial;
}
Bibliography
1. Stauffer, Dietrich. Introduction to Percolation Theory. Philadelphia: Taylor and Francis, 1985.
2. Sahini, Muhammad. Applications of Percolation Theory. Bristol: Taylor and Francis, 1994.
3. Grimmett, Geoffrey. Percolation. Berlin: Springer, 1999.
I would also like to acknowledge Thomas D. Cohen for his suggestion of the problem, backround information, and the suggestion of a change in the program that made it run much faster.
1. Lattice - A regular array of points.
2. Site - A point on a lattice. In site percolation, sites are divided into two categories: occupied and unnoccupied.
3. Bond - a connection between two neighboring sites on a lattice. In bond percolation, bonds are divided into two categories: occupied and unnoccupied.
4. p - The probability that a site in site percolation or a bond in bond percolation is occcupied.
5. Cluster - A group of occupied sites where you can travel from any site to any other site by traveling only from sites to their neighbors and only through other occupied sites.
6. Percolate - A cluster has percolated if it's size is infinite. In my simulation a cluster will be said to percolate if it touches the edge of my lattice.
7. Percolation threshold - The value of p (the probability that a site is occupied) such that all higher values of p will have some percolating clusters