2024 March 21

(As mentioned before, current MIT students should not read this material.)

- Exercises on random walks
- Percolation theory and finding the critical point
- Percolation theory and fractal dimension
- The coastline paradox
- Ant in a labyrinth: random walk with invasion percolation

Consider a region of porous rock saturated with oil. By injecting water into the rock, the oil will be displaced and forced out. We model the oil-filled pores as located on an integer grid with adjacent pores connected by narrow tubes. Water is introduced along one face of the cube, and any oil that is displaced leaves the opposite face of the cube. (For simplicity, we let the other four faces have periodic boundary conditions. It is also possible for pockets of oil to become isolated from the exit face, but we will ignore that difficulty.)

Each tube between adjacent pores has its own, random resistance to water being forced through it. Because of surface tension, if the water pressure is below a threshold, no water will pass, and above that threshold water will pass freely. As water pressure is gradually increased at the inlet, the water-filled region will expand through only the tube it touches with the lowest threshold. This continues until the water-filled region touches the outlet face, at which point any further water simply goes to the outlet, and no more oil will be displaced.

Students were provided with a python program to simulate this process and compute how much oil was displaced. Our goal was then to estimate the fraction of oil displaced when . However the program is unable to handle grids nearly that large, having a billion billion sites. Therefore we approach this task by performing simulations for many smaller values of and finding a suitable functional form that allows us to extrapolate to higher values of .

```
import invperc
N = 100
Ls = np.arange(4, 70, dtype = int)
oil = np.zeros(Ls.shape)
for i in range(N):
for j in range(np.size(Ls)):
oil[j] += invperc.invperc(Ls[j])
oil = oil / N
a, b = np.polyfit(np.log(Ls), np.log(oil), 1)
```

Based on our previous experience with percolation, we should expect to see the oil displaced to follow a power law. Graphing the results gives:

We see that the simulations for from 4 to 70 gives an excellent fit to a power-law following . At , then, we expect the fraction of oil displaced to be only 0.003959 – just 1 part in 250!

The small amount of displaced oil is due to the fact that the percolating cluster is a fractal, having dimension smaller than 3.

We previously looked at the behavior of a random walker (or equivalently, a diffusive process) on an integer lattice. In 1976, French physicist de Gennes posed the question of a random walker on a fractal percolation cluster, also called the “ant in a labyrinth” problem.

As large is important for this behavior, we fall back to 2D. Students were provided with a cluster formed by invasion percolation in a 1001 x 1000 grid, as in the previous section. In the file, 1 represents sites with water, and 0 represents sites with oil; the first column is all 1s, being the injection face.

Given this cluster, let us imagine releasing random walkers into the
invasion face and ask how far they manage to get from their starting
point within a fixed time, restricting their motion to the percolation
cluster.^{1}As the graph is not homogenous, it is important
to be clear about what exactly we mean by a random walk. I specified
that each walker attempts to move to a random adjacent site, and does
not move if that would bring it out of the cluster. I believe that in
the “correct” definition, the walker always moves to a random adjacent
site in the cluster; I’m not sure if my version gives the same results
or not. Some authors specify that there is a fixed 1/2 chance the walker
does not move at each time to avoid parity issues from the graph being
bipartite; that variation certainly is equivalent to the standard
definition. In a standard integer lattice, we expect
walkers to diffuse a distance of in time ; what about on the percolation cluster?

While somewhat noisy,^{2}and I
think there is a bug in my code for handling distance with the
wrap-around the data is clear enough to show that
diffusion on a percolation cluster is slower than on the Euclidean
lattice. One might expect that since diffusion on the standard lattice
scales as regardless of dimension, then the same
would happen on a fractal with non-integer dimension, but instead is observed, as the fractal has many turns
and dead-ends that hinder the walker.

In theoretical studies of the ant in a labyrinth, a slightly
different way of measuring the diffusion rate is usually taken: rather
than asking how far a walker travels in time , we instead ask the chance that it is at the
origin at time ^{3}This
is why usually one allows the walker not to move with probability 0.5,
as otherwise due to parity it is impossible to be at the origin when
is odd, which is slightly
annoying.. On an integer lattice of dimension this probability scales like so define the *spectral
dimension* of a graph as

where is the position of the walker at time , and is the probability it is located at the origin. Then , as expected.

What is the spectral dimension of a critical cluster? While it is not
too hard to test this numerically, as we did with a finite domain , we have a little difficulty with actually
stating the problem because of defining what we mean by “critical
cluster”. Certainly if we consider some finite cluster, its spectral
dimension is 0 (because remains above a fixed constant while
), so we must work with an
infinite cluster. For , where is the critical threshold, there is an infinite
cluster with probability 1, but its dimension is simply , the dimension of the lattice it is embedded in;
no fractal behavior is exhibited. For , the probability of an infinite cluster
is 0,^{4}This has only been proven for and , but believed to be true for all . and very strongly so: the largest
cluster in a domain of size scales like , so the bigger the area we look at the more
we “fall behind” making an infinite cluster. Therefore we must consider
specifically if we want fractal behavior.

At , again the probability of an infinite
cluster is 0. However there are arbitrarily large clusters, which
locally *appear* infinite. For any domain of size , there is a nonzero chance that a cluster spans
the whole domain; such a cluster looks infinite from the perspective of
that finite domain. Moreover, due to scale invariance, the probability
of a cluster spanning the domain does not vary with . These larger and larger clusters *look*
infinite.

While the probability of an infinite cluster is zero, that does not make it impossible, and we can condition on the even that it occurs. There are two equivalent ways we can approach this definition. For a fixed vertex , consider

- The limit as of the probability of an event E conditioned on the cluster containing escaping the local region of size , and
- The limit as from above of the probability of an event E conditioned on the cluster containing is infinite.

If the event depends only on the states of finitely many
sites, then the two limits described above are equal, and they define a
probability measure for such events , which extends to a unique probability measure on
all events, including those that depend on infinitely many sites. In
that extended probability measure, there exists a *unique*
infinite cluster containing with probability 1. This is called the
*incipient infinite cluster*. For whatever reason, the earliest
proof
of this is very specific to two dimensions (it seems to use in a
critical way that any loops in the cluster divide the plane into an
inner and outer parts, which behave independent of each other, and some
very technical computations specific to the plane) though it seems
likely to be true in all dimensions (and presumably has been proven
since that first paper came out).

Therefore, we can talk about the properties of the IIC, which within any domain of size will resemble the cluster that spans the domain, if such a cluster exists. The Alexander-Orbach conjecture states that (with probability 1) the spectral dimension of the IIC is 4/3, regardless of the dimension that the cluster is embedded in. That is, the probability that a random walker will be found at the origin scales as with time.

The Alexander-Orbach conjecture has been proven for and is now generally believed to be true for and false for , with numerical experiments showing that in 2D and in 3D.

Why ? First, observe the main difficulty of proving results in percolation theory: loops. Clusters may contain loops, or equivalently two paths within a cluster may intersect, so that the behavior of one path is not independent of the behavior of another path, making it more challenging to find the probability that there exists a path within the cluster extending to infinity. The Bethe lattice of degree is the universal covering tree of , which is to say it is the same thing as the integer lattice but ignoring all loops (e.g., going “up, up, right, right” takes you to a different place than “right, right, up, up” on the Bethe lattice). Being a tree with no loops, percolation theory on the Bethe lattice is very easy, and the Alexander-Orbach conjecture can be shown to be true.

On the integer lattice, as is increased, the critical threshold decreases. Thus the IIC becomes thinner and
thinner, despite being embedded in a bigger and bigger space; the IIC
looks more and more tree-like. The *critical
dimension* of percolation is exactly 6, which is to say that for
(or sometimes ? It seems there is some trickiness that
arises at exactly .), mean field
theory applies. In the mean-field theory, loops in the IIC are rare,
rare enough that they do not contribute to the large-scale behavior of
the cluster. In this case many of the properties of the IIC are in
agreement with properties on the Bethe lattice, which is why it is
believed the Alexander-Orbach conjecture applies on for .

While is the easiest case for studying percolation theory, the next easiest is , for a very different reason. Here, conformal field theory can be used to exactly resolve some questions, and for others allows numerical simulations of clusters that are much larger than can reasonably fit into memory by tracking large-scale properties (like the topology of their boundary) rather than individual sites. I believe the key insight here again has to do with loops: namely, that loops in 2D divide a grid into two parts that are disconnected and therefore can be analyzed independently of each other. No such luck in , where the best known results generally come from direct simulations of grids.

*Follow RSS/Atom feed for updates.*