# 12.4: Renormalization Group Analysis to Predict Percolation Thresholds

- Page ID
- 7839

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)The next analytical method is for studying critical thresholds for percolation to occur in spatial contact processes, like those in the epidemic/forest fire CA model discussed in Section 11.5. The percolation threshold may be estimated analytically by a method called *renormalization group analysis*. This is a serious mathematical technique developed and used in quantum and statistical physics, and covering it in depth is far beyond the scope of this textbook (and beyond my ability anyway). Here, we specifically focus on the basic idea of the analysis and how it can be applied to specific CA models.

In the previous section, we discussed mean-field approximation, which defines the average property of a whole system and then describes how it changes over time. Renormalization group analysis can be understood in a similar lens—it defines a certain property of a “portion” of the system and then describes how it changes over “scale,” not time. We still end up creating an iterative map and then studying its asymptotic state to understand macroscopic properties of the whole system, but the iterative map is iterated over spatial scales.

I am well aware that the explanation above is still vague and somewhat cryptic, so let’s discuss the detailed steps of how this method works. Here are typical steps of how renormalization group analysis is done:

- Define a property of a “portion” of the system you are interested in. This property must be definable and measurable for portions of any size, like a material property of matter. For analyzing percolation, it is typically defined as the probability for a portion to conduct a fire or a disease from one side to another side through it.
- Calculate the property at the smallest scale, \(p_1\). This is usually at the single-cell level, which should be immediately obtainable from a model parameter.
- Derive a mathematical relationship between the property at the smallest scale, \(p_1\), and the same property at a one-step larger scale, \(p_2= Φ( p_1)\). This derivation is done by using single cells as building blocks to describe the process at a larger scale (e.g., two-by-two blocks)
- Assume that the relationship derived above can be applied to predict the property at even larger scales, and then study the asymptotic behavior of the iterative map \(p_{s+1}= Φ( p_s)\) when scale \(s\) goes to infinity.

Let’s see what these steps actually look like with a specific forest fire CA model with Moore neighborhoods. The essential parameter of this model is, as discussed in Section 11.5, the density f trees in a space. This tree density was called \( p\) in the previous chapter, but let’s rename it \(q\) here, in order to avoid confusion with the property to be studied in this analysis. The key property we want to measure is whether a portion of the system (a block of the forest in this context) can conduct fire from one side to another. This probability is defined as a function of scale \(s\), i.e., the length of an edge of the block (Fig. 12.4.1). Let’s call this the conductance probability for now.

The conductance probability at the lowest level, \(p_1\), is simply the probability for a tree to be present in a single cell (i.e.,a 1×1 block). If there is a tree, the fire will be conducted, but if not, it won’t. Therefore:

\[p_{1}=q\label{(12.11)} \]

Next, we calculate the conductance probability at a little larger scale,\(p_2\). In so doing, we use \(p_1\) as the basic property of a smaller-sized building block and enumerate what are their arrangements that conduct the fire across a two-cell gap (Fig. 12.4.2).

As you see in the figure, if all four cells are occupied by trees, the fire will definitely reach the other end. Even if there are only three or two trees within the \(4\) area, there are

four different ways to transmit the fire through the area. But if there is only one tree, there is no way to transmit the fire, so there is no need to consider such cases. This is the exhaustive list of possible situations where the fire will be conducted through a scale-2 block. We can calculate the probability for each situation and add them up, to obtain the following relationship between \(p_1\) and \(p_2\):

\[p_{2}=\Phi{p_{1}} =p_{1}^{4}+4p^{3}_{1}(1-p_{1})+4_{1}^{2}(1-p_{1})^{2}\label{(12.12)} \]

And this is the place where a very strong assumption/approximation comes in. Let’s assume that the relationship above applies to \(4×4\) blocks (Fig. 12.4.3), \(8×8\) blocks, etc., all the way up to infinitely large portions of the forest, so that

\[p_{n+1}=\Phi{p_{s}}=p_{s}^{4}+4p_{s}^{3}(1-p_{s})+4p_{s}^{2}(1-p_{s})^{2} \ \text{for all s.} \label{(12.13)} \]

Of course this is not correct, but some kind of approximation needs to be made in order to study complex systems analytically.

Why is it not correct to assume that the relationship between the \(1×1\) blocks and the \(2×2\) blocks can be applied to \(2×2\) and \(4×4\) (and larger)? Look at Fig. 12.4.3 carefully and figure out some configurations that violate this assumption.

Anyway, now we have a relatively simple iterative map of \(p_s\), i.e., the conductance probability for a portion of the forest at scale \(s\). Its asymptotic value, \(p_{∞}\), tells us whether the fire will propagate over indefinite lengths of distance. You can draw a cobweb plot of Eq.\ref{(12.13)} again using Code 5.4, by replacing the function` f(x)`

with the following(again, make sure to also change `xmin `

and `xmax `

to see the entire cobweb plot):

This will produce the cobweb plot shown in Fig. 12.4.4. This looks quite similar to what we had from the mean-field approximation before, but note that this is not about dynamics over time, but about relationships between scales. It is clearly observed in the figure that there are two asymptotic states possible: \(p_{∞}=0\) and \(p_{∞}=1\). The former means that the conductance probability is \(0\) at the macroscopic scale, i.e., percolation doesn’t occur, while the latter means that the conductance probability is \(1\) at the macroscopic scale, i.e., percolation does occur.

Which way the system goes is determined by where you start plotting the cob webplot, i.e., \(p_{1}=q\), which is the tree density in the forest. The critical percolation threshold, \(p_c\), is seen in Fig. 12.4.4 as an unstable equilibrium point around \(p = 0.4\). The exact value can be obtained analytically as follows:

\[p_{c} =\psi(p_{c})=p_{c}^{4} +4p^{3}_{c}(1-p_{c})+4p_{c}^{2}(1-p_{c})^{2}\label{(12.14)} \]

\[0=p_{c}(p_{c}^{3}+4p_{c}^{2}(1-p_{c})+4p-{c}(1-p_{c})^{2}-1)\label{(12.15)} \]

\[0=p_{c}(1-p_{c})(-p_{c}^{2}-p{c}-1 +4p_{c}^{2}+4p_{c}(1-p_{c}))\label{(12.16)} \]

\[0=p_{c}(1-p_{c})(-1 +3p_{c}-p_{c}^{2}) \label{(12.17)} \]

\[p_{c}=0,1, \frac{3 \pm{\sqrt{5}}} {2}\label{(12.18)} \]

Among those solutions, \(p_{c} = (3−√5)/2 ≈ 0.382\) is what we are looking for.

So,the bottom lineis,if the tree density in the forest is below 38%,the burned area will remain small, but if it is above 38%, almost the entire forest will be burned down. You can check if this prediction made by the renormalization group analysis is accurate or not by carrying out systematic simulations. You should be surprised that this prediction is pretty good; the percolation indeed occurs for densities above about this threshold!

Estimate the critical percolation threshold for the same forest fire model but with von Neumann neighborhoods. Confirm the analytical result by conducting simulations.

What would happen if the space of the forest fire propagation were 1-D or 3-D? Conduct the renormalization group analysis to see what happens in those cases.