Edge of Chaos: Self-Organized Criticality

In the paper, Self-Organized Criticality: An Explanation of 1/f Noise, authors show a very simple iterative procedure which generates some interesting results. This procedure is quite easy to code up and we can verify the results. What is this procedure and what’s so interesting about the results anyway? Let’s dive into it.

Consider an integer array $z$, that uses the following evolution rule if for any $(x, y)$, $z(x, y) > 4$:

You can think of the array as ‘sand pile’ where if the height at a point, $z(x, y)$ is greater than 4, pile collapses at that point and spreads the sand to the neighboring points. This continues until all the values of the array are below 4. We want to count how many steps before the array settles down. Let’s write code to run this:

import numpy as np

def evolve(arr, critical=4):
    """
    Evolves the arr for one time step.
    Returns False if the system is stable.
    """
    bad_x, bad_y = np.where(arr >= critical)
    try:
        bad_x = bad_x[0]
        bad_y = bad_y[0]
        arr[bad_x, bad_y] = arr[bad_x, bad_y] - 4

        if bad_x > 0:
            arr[bad_x - 1, bad_y] = arr[bad_x - 1, bad_y] + 1

        if bad_y > 0:
            arr[bad_x, bad_y - 1] = arr[bad_x, bad_y - 1] + 1

        if bad_x < arr.shape[0] - 1:
            arr[bad_x + 1, bad_y] = arr[bad_x + 1, bad_y] + 1

        if bad_y < arr.shape[1] - 1:
            arr[bad_x, bad_y + 1] = arr[bad_x, bad_y + 1] + 1

        return True
    except IndexError:
        return False


def evolve_until_stable(arr):
    """
    Evolve the array until it is stable.
    Return number of steps to the stability.
    """
    num_steps = 1
    while evolve(arr):
        num_steps = num_steps + 1
        
    return num_steps

Let’s initialize the array randomly with a large maximum value and evolve it until stable.

n = 20
arr = np.random.randint(low=0, high=10, size=(n, n))
evolve_until_stable(arr)

Array stops evolving when it is barely stable. Authors of the above paper call this state ‘self-organized criticality’. This is how it looks like:

How does adding another ‘sand grain’ to this state i.e. $z(x, y) \rightarrow z(x, y) + 1$, affect the system? If the grain falls at the places where height is <3, nothing happens. We can see that there are a fair bit of 3s are next to each other. If the sand grain falls on these clusters, they can cause a chain reaction (‘avalanche’) dramatically changing the state!

Let’s keep on adding sand grains at random places and measure the distribution of sizes of avalanches.

def perturb(arr):
    x = np.random.randint(low=0, high=arr.shape[0])
    y = np.random.randint(low=0, high=arr.shape[1])
    arr[x, y] = arr[x, y] + 1

# generate a self organized criticality
n = 20
np.random.seed(0)
arr = np.random.randint(low=0, high=10, size=(n, n))
evolve_until_stable(arr)

num_sim = int(1e5)

# perturb and measure the avalanche sizes.
avalanche_sizes = []
for _ in range(num_sim):
    perturb(arr)
    avalanche_size = evolve_until_stable(arr)
    avalanche_sizes.append(avalanche_size)

Let’s draw the histogram of avalanche_sizes:

Most of the avalanches are small but there are a few really large avalanches. Nothing special right? Let’s change both the axes to log.

That’s weird – we see a line! Tail does not follow the line exactly because of boundary effects and sampling errors (sample size is $10^5$ in this case). If we represent the size of avalanche by $n$, we have

This distribution is what is called power law. There are a lot of names to this distribution: mathematicians call it pareto distribution, while physicians call it $1/f$ noise. It shows up in lot of places from economics, geology to world wide web. Pareto law, which states 20% events cause 80% consequences follows from the power law.

Perturbations to a minimally stable state seems to be generating an universal: power laws. Is this the mechanism underlying the complex systems like earthquakes and life?

This idea is not new. Ilya Prigogine, a physicist and Nobel laureate Stuart Kauffman, a mathematical biologist suggest that life and other complex systems seem to be operating at edge of chaos and order. Author of the paper in question, Per Bak goes as far as to suggest brain is a self-organized criticality. I wonder if we’ll ever get to the answer!