Ant in a labyrinth: random walk with invasion percolation

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

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 $L \times L \times L$ 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 $L = 10^6$ . 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 $L$ and finding a suitable functional form that allows us to extrapolate to higher values of $L$ .

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 $L$ from 4 to 70 gives an excellent fit to a power-law following $0.582 L^{2.63878}$ . At $L = 10^6$ , 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.

Ant in a labyrinth

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 $L$ 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.¹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 $\sqrt t$ in time $t$ ; what about on the percolation cluster?

While somewhat noisy,²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 $\sqrt t$ regardless of dimension, then the same would happen on a fractal with non-integer dimension, but instead $t^{0.45}$ 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 $t$ , we instead ask the chance that it is at the origin at time $t$ ³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 $t$ is odd, which is slightly annoying.. On an integer lattice of dimension $d$ this probability scales like $t^{-d / 2}$ so define the spectral dimension of a graph $G$ as

$d_s(G) = -2 \lim_{t \to \infty} \frac {\log P(X(t) = 0}{\log t}$

where $X(t)$ is the position of the walker at time $t$ , and $P(X(t) = 0)$ is the probability it is located at the origin. Then $d_s(\mathbb Z^d) = d$ , 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 $L = 1000$ , 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 $P(X(t) = 0)$ remains above a fixed constant while $\log t \to \infty$ ), so we must work with an infinite cluster. For $p > p_c$ , where $p_c$ is the critical threshold, there is an infinite cluster with probability 1, but its dimension is simply $d$ , the dimension of the lattice it is embedded in; no fractal behavior is exhibited. For $p < p_c$ , the probability of an infinite cluster is 0,⁴This has only been proven for $d = 2$ and $d \geq 19$ , but believed to be true for all $d$ . and very strongly so: the largest cluster in a domain of size $L$ scales like $\log L$ , so the bigger the area we look at the more we “fall behind” making an infinite cluster. Therefore we must consider specifically $p = p_c$ if we want fractal behavior.

At $p = p_c$ , again the probability of an infinite cluster is 0. However there are arbitrarily large clusters, which locally appear infinite. For any domain of size $L$ , 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 $L$ . 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 $v$ , consider

The limit as $n \to \infty$ of the probability of an event E conditioned on the cluster containing $v$ escaping the local region of size $L$ , and
The limit as $p \to p_c$ from above of the probability of an event E conditioned on the cluster containing $v$ is infinite.

If the event $E$ 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 $E$ , 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 $v$ 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 $L$ 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 $t^{-2/3}$ with time.

The Alexander-Orbach conjecture has been proven for $d \geq 19$ and is now generally believed to be true for $d > 6$ and false for $d \leq 6$ , with numerical experiments showing that $d_s \approx 1.3100 < 4/3$ in 2D and $d_s \approx 1.32$ in 3D.

Why $d > 6$ ? 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 $2d$ is the universal covering tree of $\mathbb Z^d$ , 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 $d$ is increased, the critical threshold $p_c$ 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 $d > 6$ (or sometimes $d \geq 6$ ? It seems there is some trickiness that arises at exactly $d = 6$ .), 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 $\mathbb Z^d$ for $d > 6$ .

While $d \geq 6$ is the easiest case for studying percolation theory, the next easiest is $d = 2$ , 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 $d = 3, 4, 5$ , where the best known results generally come from direct simulations of grids.

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.↩︎
and I think there is a bug in my code for handling distance with the wrap-around↩︎
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 $t$ is odd, which is slightly annoying.↩︎
This has only been proven for $d = 2$ and $d \geq 19$ , but believed to be true for all $d$ .↩︎

Follow RSS/Atom feed for updates.