Two Dimensional Random Walk on Percolation Clusters
George M Paily, Shivakumar Jolad,
Sangamitra Neogi
Department of Physics, Pennsylvania State University, University Park,
PA 16803
Report in PDF form(248kb)
Java
Applet- Percolation Cluster
Java
Applet-Cluster marking
Java
Applet-Random walk on Percolation Cluster
Introduction
Random walk is
mathematical formulation of the intuitive idea of taking successive steps, each
in a random direction. Problems involving Random walks are ubiquitous in
nature. They can be used as good models to understand various phenomenon's like
Brownian motion, diffusion processes. In polymer physics, random walk helps to
describe the ideal chain. It also finds its application in various other fields
like economics, brain research etc. The behavior of random walks depends on
certain parameters like spatial dimensions of the walk, constraints put on the
walk. Unconstrained random walk typically belongs to the universality class
where the root mean square distance varies asymptotically as square root of the
number of steps taken 
and is independent of the dimensions of the walk. On the
other hand the number of returns to origin and the number of distinct sites
visited in N steps depend on dimensions of the walk. In these higher
dimensions Random walks show a fractal structure. One can define dimensions
like the fractal dimension, fracton dimension etc on these walks. These
dimensions and related exponents define the universality class of the Random
Walk. We consider Brownian motion as for example. One of the well known
structures in Brownian motion curve has a fractal dimension of 2 and behaves
like a space filling curve.
The characteristic of walk also changes when one imposes constraints. One such constraint is to restrict the walk on a `Percolation cluster'. In this article we study the Random Walk on an invasion percolation cluster (and estimate the dimension parameters using its asymptotic behavior. We show that this belongs to different universality class with fracton dimension 4/3.
A percolation model
is a collection of points distributed in space with certain pairs (usually the
adjacent neighbors) connected [2]. The distribution of these points can be
modeled by assigning a site destruction probability p. A simple
linkage can be implemented by linking adjacent occupied sites. Such linked points
are said to be connected. All these points of the distribution may be
partitioned into clusters such that pairs of points in the same
cluster are connected but there is no path between points of different
clusters. The size of the cluster and number of clusters in a given percolation
model depends critically on the site occupation probability. If the percolation
model size is such that boundary(surface) effects are
negligible, one can effectively treat the model as a system with infinite sites
and unbounded volume. In such a system, the size of the cluster may become
infinite at some critical density of the linkages. One can then define the percolation
probability as the probability that a given percolation model has an
infinite cluster. The percolation probability gives the chance that one can
find an infinite sized cluster. This percolation probability P(p)
critically depends on p (site destruction probability). When p>pc
(pc is the critical probability), 
the
system is said to be in the percolating state where one can find clusters of
infinite extent. This situation is exactly similar to phase transition from
disordered to ordered phase. One can analogously define all critical exponents
to this problem. For example, the rms deviation from center 
, is the analogue of correlation length (both diverge at the
transition), the distinct number of sites in the cluster S(p) is the
analogue of susceptibility.
Random Walk on Percolation Cluster
Percolation cluster at or beyond the transition point provides a constrained arena for Random Walk. The situation of the walker is that of an ``ant in the labyrinth''. Here the walker (an `ant') starts at an arbitrary point on the cluster and tries to move randomly to the nearest sites. If the randomly chosen direction of othe next step leads to an occupied site, he moves and the steps increment by 1. If he doesn't find a site he stay's there itself and the step is incremented. After long number steps one can analyze the asymptotic behavior of such a walk. The rms displacement, number of returns to the origin and number of distinct sites visited for the walk show some power law dependence on number of steps(not all these exponents are independent).
Simulation
Simulation
of 2D Random Walk
Our starting point
for simulation was implementing a 2 dimensional random walk and checking to see
if it agrees with the expected behavior. The following figures[Fig.1-2]
show two typical Random Walks. These figures are typical of Brownian motion.
One of the measure of its asymptotic behavior is the rms displacement, which
when plotted shows the expected behavior of 
as number steps N
becomes large[Fig.3].
Fig 1- Random walk in 2D trial 1 Fig 2- Random walk in 2D trial 2.
Fig3. Mean square displacement versus number of steps in 2D RW
Creating
infinite Percolation cluster
The second step is growing a percolation cluster by destroying sites on a 2D lattice. We chose the default value of the lattice to be 125X125. After some critical probability the cluster size grew to a big size which can be considered as infinite cluster. If N is the number of steps in random walk and M is the size of cluster (maximum rms distance from origin) then one of the requirement for effective infinite cluster random walk is M>>N. The program also identifies individual cluster and plots them in different color. One can show that near the threshold probability the size of clusters formed grow rapidly indicating a transition from disconnected (non conducting) to connected (conducting) phase (disordered to ordered phase). The following figures [Fig.4-7] show cluster formation and clusters when p< pc and p> pc.
Fig 4. Percolation Model when p< pc. Fig 5. Percolation Cluster when p< pc
Fig 6. Percolation model when p> pc. Fig 7. Percolation cluster when p> pc
We also wrote a program to count the number
of clusters and size of the cluster. At the threshold probability one
expects that the size of the largest cluster to suddenly grow and show a
discontinuous behavior. We also expect the cluster number to be close to 1 when p approaches zero. The following figures [Fig.8-9] plot the size of
cluster and numbers of clusters versus the site destruction probability.
Fig 8. Cluster size as
function of p
Fig 9. Cluster number as function of p
Imposing
Random walk on Percolation Cluster
The next step is to impose the random walk on the percolation cluster. The initial point of the RW is chosen such that it lies on one of the cluster. Physically one expects that there is high probability that it lands on infinite cluster (if it exists). The lattice size is chosen to be much bigger than the average size of the random walk. In our case on a 125X125 lattice we had a 1000 steps random walk. We ran around 4000 such walks and did an ensemble average of them. The time of execution depends mainly on the lattice size and site occupation probability. Small increase in lattice width lead to large increases in the execution time. The dynamic display of clusters with different colors and the display of individual random walks take a lot of execution time.
Hence we did separate programs-
(1) to Illustrate cluster formation and to dynamically display 2D random walk.
(2) to do calculations (ensemble averages) on the
random walks
(3) to perform calculations on Percolation cluster- like cluster size and
cluster number.
The results and calculations are shown in the following sections.
Asymptotic behavior: Theoretical predictions and
simulation results
RMS
displacement
After large number of steps t the mean square
displacement 
of the RW on
Percolation behaves as
Here the exponent dw
is related to fractal dimension D of the cluster and fracton 
dimension of the
walk by
Alexander and Orbach
conjectured the value of as = 4/3 [3]. Various simulations have supported this.
Our results for the best estimate can be read by the following figure[Fig.10]. It was generated for 125X125
lattice with 1000 step walks and averaged over $4000$ runs. We
evaluated the cluster at the expected transition point p=0.38. The
following figure shows the plot of our best linear fit for 
versus 
. It gives dw=2.801
which is very close to the expected value of 2.844!
Fig 10. log(RMS distance)/2
versus log(t). Fig 11. log(number of distinct sites) versus log(t)
Number of distinct sites Visited
The number of distinct sites visited St after time (steps) t
varies asymptotically as
The following figure illustrates the asymptotic behavior along with a line fit. Our simulations gave slope of 0.5919 which is close to the expected value of 0.66, but still there is significant difference which we are not able to explain at this time.
Return
to Origin
Probabaility of returns to origin after steps t, P0(t) decreases asymptotically as
Fig 12. Return to Origin
We had to fit to a parabolic fit(2nd order) to this
data so as to account for slight curvature seen. But we notice the linear term
was dominant and has value of 0.6452
which gave 
of 1.29 which is
very close to the expected value of 1.33
Conclusion
In summary we have shown that our simulation of Random walks on Percolation
clusters behaved nearly as expected. We could calculate the various exponents
from this simulation and established that the fracton and fractal dimension of
such Random walks are different from the unconstrained walks in 2 Dimension.
Such constrained walks have wide applicability. This new universality class
model can be used to describe various phenomena ranging from mobile networks to
conduction in gels.
Acknowledgment
We would like to acknowledge the use of the website
www.opensourcephysics.org, using its templates we were able to conduct this
project. We would like to thank Prof. Jorge Sofo for helpful discussions and
invaluable suggestions.
Bibliography
[1] J F McCarthy, Random walks on invasion percolation cluster, J.
Phys. A: Math. Gen, 21(1988)
[2] J
[3] Alexander S and Orbach R, J. Phys. Lett, 43 L625, 1984
[4] P Argyrakis and R. Kopelemn, Random walk on Percolation clusters,
Phys. Rev. B, 29, 511, 1984
[5] Mandelbrot, Benot B. The Fractal Geometry of Nature.
[6] www.opensourcephysics.org