Percolation

Open cells at random and find the critical chance at which clusters join and water passes through.

  • Blocked
  • Open, one color per cluster
  • Cluster joining top and bottom
  • Water
100%

Each cell is open with chance p. Just above a critical chance, open clusters suddenly join into one that spans the board and water poured in at the top gets through. Drag across the board to open or close cells and try to block or connect the flow; Rerun keeps your changes.

Setup
Lattice
120 × 120 cells
Model
0.593
View
60 cells per second

How is Percolation working for you?

About Percolation

Introduced
Broadbent and Hammersley, 1957
Square sites
Threshold about 0.592746
Square bonds and triangular sites
Threshold exactly 1/2
Board
Up to 200 × 200 cells

Percolation is the mathematics of getting through a random maze: water seeping through coffee grounds or porous rock, fire crossing a patchy forest, a disease finding a path through a population. The model is simple. Each cell of a board is open with chance p and blocked otherwise; open cells that touch form clusters; and the question is whether some cluster connects the top of the board to the bottom. Simon Broadbent and John Hammersley introduced percolation theory in 1957, and it has become a model of phase transitions, where a small change in one quantity causes a sudden change in behavior.

Slide p up slowly and watch. Below a critical chance the open cells form many small, separate clusters and the water poured in at the top soon stops. Just above it, the clusters join into one huge cluster, highlighted in gold, that spans the board, and the water gets through. For square sites the critical chance is about 0.5927, a value computed to many digits by Mark Newman and Robert Ziff in 2000; for links between square sites (bond percolation) and for triangular sites it is exactly 1/2, which Harry Kesten proved for bonds in 1980. Clusters are colored the way Hoshen and Kopelman's labeling method finds them.

The chart shows how sudden the change is. In the background the tool grows hundreds of fresh random boards of the same size from empty, opening cells one at a time in random order as Newman and Ziff suggested, and records the chance at which each first spans. The share of boards that span at each p forms an S-shaped curve that steepens around the critical chance, and gets steeper still on bigger boards. Drag across the board to open or block cells, compare the three lattices, and export the spanning chances as CSV.

How to use Percolation

  1. Set the chance. Move Chance open (p) to change the share of open cells. The board keeps the same random numbers, so raising p only opens more cells; press Jump to the threshold to go straight to the critical chance.
  2. Pour water. With Pour water on, water enters along the top row and spreads through open cells, one layer per step. The counter says whether it got through; Flow speed sets how fast it spreads, 60 cells per second by default.
  3. Read the colors. Each cluster of connected open cells has its own color, blocked cells are dark, and a cluster that spans from top to bottom is gold.
  4. Compare lattices. Lattice switches between square sites, square bonds (every cell is there and the links between neighbors open with chance p) and triangular sites, drawn as bricks with six neighbors each.
  5. Edit the board. Drag across the board to open or block the cells (or, for bonds, the links) you pass over: try to cut the spanning cluster or join two clusters. Rerun pours the water again from t = 0 over the board as edited; Restart clears your edits and starts the board again; Reset also returns every setting to its default. A share link carries your edits.
  6. Read the chart. The curve shows the share of random boards this size that span at each chance, built up from up to 400 boards; the circle marks your current p, and the vertical line marks the critical chance: about 0.5927 for square sites (Newman and Ziff, 2000) and exactly 1/2 for square bonds and triangular sites.
  7. Export. Save a PNG, a video or GIF of the water flowing, or the spanning chances as a CSV file. With Pour water on, Record full run pours again from the top and records until the water stops; without it, Record 30 s from the start records the first 30 seconds.

Frequently asked questions

What is percolation?

The study of connections in random structures. Cells (or links) are open at random with chance p, and percolation asks whether the open ones join into a path from one side to the other. It models fluids moving through porous materials, the spread of fires and epidemics, and electrical conduction in mixtures.

What is the percolation threshold?

The critical chance at which a spanning cluster first appears on a very large board. For site percolation on a square lattice it is about 0.592746; for bond percolation on a square lattice and for site percolation on a triangular lattice it is exactly 1/2. Below the threshold a spanning path almost never exists on a big board; above it, one almost always does.

Why is the change so sudden?

Because it is a phase transition. On an infinite board the chance of a spanning cluster jumps from 0 to 1 at the threshold, like water freezing at a temperature. On a finite board the jump is smoothed into the S-shaped curve in the chart, which gets steeper as the board grows.

Why is the threshold exactly 1/2 for bonds and triangles?

Symmetry. On a square bond lattice, an open path from top to bottom exists exactly when no blocked path runs across from side to side in a matching dual lattice, and the dual of the square lattice is another square lattice. The triangular site lattice has a similar property. At p = 1/2 open and blocked are equally likely, so the two kinds of crossing balance.

What does this have to do with forest fires and epidemics?

If each tree catches fire from a burning neighbor with some chance, or each contact passes on a disease with some chance, the spread is a percolation process: below the threshold an outbreak stays small, above it, it can sweep across. That is why reducing the chance of passing it on a little can stop an outbreak completely.

How does the chart know the chance of spanning?

It grows random boards from empty: cells open one at a time in random order, and a fast union-find structure tracks the clusters, so each board reveals the exact fraction of open cells at which it first spans. Counting how many boards span at or below each p gives the curve, the method Newman and Ziff described in 2000.

References

  1. Broadbent, S. R., & Hammersley, J. M. (1957). Percolation processes: I. Crystals and mazes. Mathematical Proceedings of the Cambridge Philosophical Society 53(3), 629–641.
  2. Hoshen, J., & Kopelman, R. (1976). Percolation and cluster distribution. I. Cluster multiple labeling technique and critical concentration algorithm. Physical Review B 14(8), 3438–3445.
  3. Newman, M. E. J., & Ziff, R. M. (2000). Efficient Monte Carlo algorithm and high-precision results for percolation. Physical Review Letters 85(19), 4104–4107.
  4. Stauffer, D., & Aharony, A. (1994). Introduction to Percolation Theory (2nd ed.). London: Taylor & Francis.