Percolation theory: percolation on a square lattice

Figure 1. Percolation on a 100×100 square lattice at p=0.3, 0.5, 0,7 (in the order of top to bottom). The red squares are ones that can be reached from the top or bottom by going only on filled squares.

In the previous post, we introduced the basic concepts of percolation theory. Here we define the terminologies formally. Let $E$ denote the edge set of a graph $\wedge$ . We take $\Omega = \prod_{e\in E} \{0,1\}$ as a sample space, points in which are represented as $\omega=(\omega(e):e\in \mathbb{E}^d)$ and are called configurations. A bond $e$ is open in the configuration $\omega$ if $\omega(e)=1$ and is closed if $\omega(e)=0$ , so configurations correspond to open subgraphs. We take $F$ to be the $\sigma-$ field of subsets of $\Omega$ generated by the cylinder sets. The associated probability measure is going to be the product measure with density $p$ on $(\Omega, F)$ ,

$P_p=\prod_{e\in E} \mu_e$

where $\mu_e$ is Bernoulli measure on {0,1}, given by $\mu_p(1)=p$ and $\mu_p(0)=1-p$ . We can take $\Omega$ to be the set of possible outcomes of our random subgraph and take $P_p$ to be describing its distribution. We can basically ignore the measure-theoretic details above but take note that we do use the notation $P_p$ to describe probabilities when the parameter used is $p$ .

Let us recall the definition critical probability, $p_H =$ sup $\{p:\theta(p)=0\} =$ inf $\{p:\theta(p)>0\}$ . We now present a basic result in probability theory.

Theorem 2.1 Suppose that ${X_n}$ is a sequence of independent random variables. Let A be an event in the $\sigma$ -field generated by ${X_n}$ . Suppose that the event A is independent of each finite subset of ${X_n}$ , then $\mathbb{P}(A)$ is 0 or 1 .

This is known as Kolmogorov’s 0-1 law. In percolation, we know that each site or bond has an independent probability $p$ . Let $E$ be an event that there is an infinite open cluster. The event $E$ is invariant under finite changes of sites or bonds. Thus, Kolmogorov’s 0-1 law implies that $\mathbb{P}$ (E) is either 0 or 1.

If $p<p_H$ , then

$P_p(E)\leq \sum_{x}P_p(|C_x|=\infty)=\sum_{x}\theta_x(p)=0$

If $p>p_H$ , then

$P_p(E)\geq P_p(|C_x|=\infty)=\theta_x(p) > 0$

for some site $x$ , implying that $P_p(E)=1$ . In this case, we say that percolation occurs.

Let’s sum up what we have shown so far with an analogy. Consider the case of water moving through a very large medium (so large that it will take infinitely long for water to reach the surface from an origin inside the medium). Let the probability that a pore is big enough for water to pass through be $p$ . If the medium is made of less porous material, the pores having small $p$ are less likely to be open for the water to flow through, so any open path that water travels through will likely be short. However, if it is made of more porous material with higher $p$ , there are more open channels, so water can travel through a longer path from the origin. It is obvious to see that as $p$ increases, it is likely that, eventually, water will travel infinitely far. We have observed that there is a critical probability $p_H$ representing a threshold for such an event to occur. If $p>p_H$ , then there is a positive probability that the path that water travels through is infinite. Kolmogorov’s 0-1 law guarantees that if $p>p_H$ , an infinite path must exist inside the medium, though in our case, water may not flow in that path (as there can be many disconnected open paths inside the medium and, base on our assumption, water only flow in one of them).

Figure 2. A sketch of the structure of a two-dimensional porous medium. The lines indicate open paths. Comparing both graphs, we see that water flows in a shorter path in a less porous medium with a lower value of p.

We see that on either side of the critical probability, the global behavior of the system is fundamentally different. And at critical probability, a sharp transition takes place which transforms the behavior of the system from one form to the other. Thus, the existence of a critical probability makes percolation a mathematically interesting and rich subject.

Next, we continue with our study of percolation on $\mathbb{Z}^2$ . First, we want to show that bond percolation on $\mathbb{Z}^2$ is non-trivial: $0<p_H<1$ . Let $\mu(\wedge;x)$ be the number of self-avoiding walks in $\wedge$ starting at $x$ . In graph theory, a self-avoiding walk is also known as a path. As $\mathbb{Z}^2$ is 4 regular, the number of self-avoiding walks of length $n$ starting at the origin 0 is $\mu_n=\mu_n(\mathbb{Z}^2)=\mu_n(\mathbb{Z}^2;0)\leq 4\times 3^{n-1}$ , since there are 4 choices for the first step and at most 3 choices in the later steps.

Theorem 2.2 For bond percolation in $\mathbb{Z}^2$ , we have $p_H \geq \frac{1}{3}$ .

Proof Let $F_n$ be the event that there is an open cluster $C_0$ of size $n$ starting at the origin 0 where each bond is open with probability $p$ . Then the probability that all bonds are open is $p^n$ . For every site $x \in C_0$ , there is at least one open path from from 0 to $x$ . Thus, we have

$P_p(F_n)\leq \mu_n p^n= \frac{4}{3}(3p^n)$

For $p<\frac{1}{3}, (3p^n)<1$ . Since ${|C_0|=\infty}\subseteq F_n$ $\forall$ $n$, let there be an infinite cluster from the origin with $p<\frac{1}{3}$ , we have

$P_p(|C_0|=\infty)=\lim_{n\rightarrow\infty}P_\textit{p}(F_n)\leq \lim_{n\rightarrow\infty} \frac{4}{3}(3p^n)=0$

This is the equivalent to saying if $p<\frac{1}{3}$ , $\theta(p)=0$ . By definition of $p_H$ , it follows that $p_H \geq \frac{1}{3}$ .

$\square$

We now consider an upper bound. We will make use of a key result from graph theory.

Lemma 2.3 (Grimmett) Let $C$ be a vertex set of a connected subgraph of $\mathbb{Z}^2$ . $|C|<\infty$ if and only if $\exists$ a simple cycle with $C$ in its interior.

No proof will be provided here, but by drawing some pictures we can convince ourselves that it is very believable. Looking at figures 3 and 4 will also be helpful.

Theorem 2.4 For bond percolation in $\mathbb{Z}^2$ , we have $p_H \leq \frac{2}{3}$ .

Proof The first thing we do is to introduce the dual $\wedge^*$ of a graph $\wedge$ drawn in the plane has a vertex for each face of $\wedge$ and an edge $e^*$ for each edge $e$ in $\wedge$ . When $\wedge=\mathbb{Z}^2$ , we take $\wedge^* = \mathbb{Z}^2+(\frac{1}{2},\frac{1}{2})$ , which is isomorphic to $\wedge$ . We call an bond in the dual graph $(\mathbb{Z}^2)^*$ open if and only if the corresponding bond in the original graph $\mathbb{Z}^2$ is closed. If the set of open bonds in $\mathbb{Z}^2$ are given by $P_p$ , then the distribution of the set of closed bonds in $(\mathbb{Z}^2)^*$ will also be given by $P_p$ . An \textit{open dual cycle} is a cycle in the dual graph consisting of dual bonds that are open.

Now that we have defined all the necessary terms. Suppose that $p>\frac{2}{3}$ , let $L_k$ be the line segment joining the origin to the point $(k,0)$ , and let $S$ be a dual cycle surrounding $L_k$ , which has a length $n$ . Then $S$ must contain a dual bond $e^*$ crossing the positive $x$ -axis at some coordinate between $(k+\frac{1}{2},0)$ and $(\frac{1}{2}(n-3),0)$ . This means that we have less than $\frac{n}{2}$ choices for $e^*$ . As the rest of S is a path of length $n-1$ in the dual lattice, we have shown that the number of cycles around the origin of length $n$ is at most $\frac{n}{2}\times 4(3^{n-1})$ . Let $A_n$ be the event that there exists an open dual cycle surrounding $L_k$ , since dual bonds are open with probability $1-p$ , we have

$\sum_{n=4}^{\infty} P_p(A_n) \leq \sum_{n=4}^{\infty}\frac{2n}{3}(3(1-p))^n$

Since $3(1-n)<1$ , the sum is convergent. We can choose a $N$ so that $\sum_{n\geq N}^{\infty}\frac{2n}{3}(3(1-p))^n <1$ . Now, let $E_1$ be the event that the $N$ bonds in the line segment $L_N$ are open. Let $E_2$ be the event that there are no open dual cycles surrounding $L_N$ . Since $\sum_{n=4}^{\infty} P_p(A_n)<1$ , $P_p(E_2)>0$ . If both $E_1$ and $E_2$ holds then $|C|=\infty$ by Lemma 2.3. Since $E_1$ and $E_2$ are independent, we have

$\theta(p)\geq P_p(E_1 \cap E_2) = P_p(E_1)P_p(E_2) = P_p(E_2)p^N >0$

Since $p>\frac{2}{3}$ , by definition of $p_H$ , it follows that $p_H \leq \frac{2}{3}$ .

$\square$

Figure 4. A finite open cluster at the origin, surrounded by an open dual cycle (corresponding to closed bonds in the original lattice)

We have shown that the critical probability $p_H$ for $\mathbb{Z}^2$ is in between $\frac{1}{3}$ and $\frac{2}{3}$ , so there exists a non-trivial critical phenomenon. On the basis of Monte Carlo simulations, it was suggested that the critical probability should be $\frac{1}{2}$ . In the next post, we will show that the critical probability for $\mathbb{Z}^2$ is in fact $\frac{1}{2}$ .

Percolation theory: percolation on a square lattice

Like this:

Related

Leave a ReplyCancel reply

Share this:

Like this:

Related

Leave a ReplyCancel reply

Discover more from