 |
  Imagine a two dimensional array of any size that you want. Figure 1a. shows a five by five array (its just an example, it doesn't have to be five by five). Now, assign a random number between zero and one to each element in the array (Figure 1b.) Every element which is over a certain value gets filled in and every element below that value gets left blank (we use the value of .5 in Figure 1c.) You can forget all those random numbers now, because all we care about is whether or not a square is filled (Figure 1d.)
 Now try to see if you can get from one side of your array to the other by moving from filled square to filled square. In a typical percolation experiment you can only more forward, backward, left or right one square at a time. (In Figure 1d. you wouldn't be able get from the top to the bottom or from the left side to the right side.) In our experiment, you don't have to go to a square that is directly touching the square you're on. We let you jump from square to square. If, for example, we say that you can jump 1.5 times the length of a square, you can get to ANY of the squares immediately around your square (Figure 2.)
 If we say that you can jump 2 times the length of a square, you can jump right over an empty spot and get to a filled square on the other side. In Figure 1d., you could start in the lower left corner and go forward a square, jump over the void, go right a square, jump up and to the right, and then you're across. Now that you know all about this complex and complicated jumping stuff, we can do some experiments. If you'll remember back a few minutes, we decided which squares were filled in and which were left blank by choosing a certain value (we chose point 0.5) We could have chosen a different value. If we had chosen a lower value, more squares would be filled in. If we had chosen a higher value, fewer squares would be filled in. Since the numbers in the elements are completely random and evenly spread out, changing this value is like changing the probability that a square is filled in. A high value corresponds to a low probability. A low value corresponds to a high probability.
For a slightly larger array (like an infinite one) we want to find the probability at which point it first becomes likely that you can get from one side of the array to the other. We then want to find what effect jumping has on this value.
 To take the statistics, two routines were created using the IDL programming language. The first would step through "filled" probabilities, create an array of random numbers, then label each cluster using a recursive algorithm. The algorithm would mark the initial square with the current label, and then check each square within a radius of the specified jump distance to see if it should also be marked. If it found one that hadn't been marked, the routine would be called again starting with that square. Once all the repetitions are done, one entire cluster had been marked. The main routine would then look for an unmarked cluster, and start the subroutine again. Once this was done, the main routine could then check for the presence of the same label on both sides of the array. For step size of 1, there are much more effecient algorithms one could use to perform the labelling, but those don't apply nearly as well to cases where jumps can be discontiguous. Here's the code.
 The results of roughly 100 hours of cumputer simultation can be broken down as follows.
 The above graph plots the probability that a spanning cluster will appear, on the verticle axis, against the probability that a square is filled on the horizontal axis (the probablility is normalized to 1, so 0.1 is 10 percent...). Going from left to right, the lines represent step sizes of 6.0, 5.5, 5.0, 4.5, 4.0, 3.5, 3.0, 2.5, 2.0, 1.5, and finally 1.0. As expected, the probability of having a spanning cluster is higher for longer step sizes. This makes sense, because it is easier to get across the grid if you can jump over holes or jump between squares that weren't accessible at at lower setp sizes.
 It should be apparent from the first plot that the critical probablility is decreasing with increasing step size. In the plot above, the critical probability is plotted against the step size. It looks as though the data is following some sort of power law. As the step size is increased, the number of squares which can be jumped to increases as the step size squared. It seemed to us, therefore, that this curve should follow a one over step size squared pattern.
 The plot above shows a line fit to the data based on our assumption of a 1/r^2 dependance. The data is fairly linear and well fit to the line. This would certainly tend to indicate that our assumption was correct. To summarize, our assumption was that the number of squares which can be jumped onto scales like the square of the step size. The more squares which can be reached in a given step, the more easily the array or grid can be crossed. The critical probability should (and does in fact seem to) scale like one over the step size squared.
 The final plot compares the results of three different types of spanning cluster identification algorithms. All three lines are based on a step size of 2. The cyan line is the result of the standard procedure which simply looks for a normal spanning cluster. The light green line is the result of the renormalization procedure which renormalizes 2x2 groups of squares into a single squares. The last line is the result of the renormalization procedure which renormalizes 3x3 groups of squares into single squares. As we would hope, the standard program and the renomalization program using 3x3 groups return roughly the same result. The other renormalization procedure, however, returns a value that is significanly different. This is most likely due to the fact that the step size is as big as the renormalization grid. Copyright © 1996 Allison Elliott, David Gibson, and Paul Steele. All Rights Reserved |
The other routine decided if there was a spanning set through the process of renormalization. It would group the elements of the array together in squares of 2 or 3, and then check each group to see if it had a spanning cluster. If it did, the output square corresponding to that group was 1. If not, it was zero (Figure 3). Thus the dimensions of the square were reduced by a factor of 2 or 3 for each iteration. This process was repeated until the output was a single square, and if the value was one, there was a spanning set, and if it was zero, there was not. Here's the