The Threshold That Changes Everything

Drag the p slider slowly through 0.59. Below it, the grid breaks into isolated islands. At 0.5927, a cluster spanning top to bottom first appears. The spanning cluster toggles on: a path now threads the entire medium. That transition from none to one is the whole subject.

The question that launched percolation theory was about coffee. Or rather, Simon Broadbent (a statistician at the UK Coal Board) described the problem in terms of fluid finding a path through a porous stone, but the underlying question is the same one that faces anyone pouring water through grounds and wondering why it sometimes channels and sometimes doesn't. In 1957 Broadbent presented the problem to John Hammersley at a symposium and they published a foundational paper together in the Mathematical Proceedings of the Cambridge Philosophical Society. The difference between their model and classical diffusion was precise and consequential: in diffusion, the randomness is in the fluid; in percolation, the randomness is in the medium. Each site in the lattice is occupied with probability p, independently of every other site. The fluid goes where it can.

What they proved, and what physicists and mathematicians spent the next fifty years making rigorous (is that there exists a critical threshold p_c at which the behavior of the system changes qualitatively. Below it, all clusters remain finite: any path through the medium eventually hits a blocked site and terminates. Above it, a single cluster of infinite extent (or, on a finite lattice, one that spans from edge to edge) first appears. For site percolation on a square lattice, that threshold is approximately 0.592746. The number itself is not derivable from simple combinatorics; it has been computed to extraordinary precision via Monte Carlo simulation and, more recently, graph polynomial methods, which pin it to 0.592746050792 with uncertainty only in the last two digits. The threshold for bond percolation on the same lattice is exactly 1/2, which Kesten proved in 1980) one of the few cases where the exact value is known analytically.

The visual behavior of the system at criticality is what makes percolation compelling beyond its mathematical content. Exactly at p_c, the largest cluster is not a compact blob but a fractal: it has the same qualitative structure at every scale, branching and thinning without resolving into either a dense mass or a sparse dust. The fractal dimension of the critical cluster in two dimensions is approximately 91/48 ≈ 1.896, a value that holds regardless of whether the underlying lattice is square, triangular, or hexagonal. This universality (that the exponents depend only on spatial dimension, not on lattice geometry) was the discovery that connected percolation to the broader apparatus of statistical mechanics. The Ising model at its critical temperature, percolation at p_c, and several other systems in two dimensions share the same critical exponents, which belong to what physicists call a universality class.

The artifact implements site percolation with a union-find algorithm, which is the standard approach for labeling clusters in a single pass without BFS or DFS. Each occupied site that has no occupied neighbors to its left or above becomes a new singleton component. Each site that has occupied neighbors merges their components. The union step uses union by rank with path compression, keeping nearly every find operation at amortized O(α(N)), essentially constant:

function find(x){
  while(parent[x] !== x) x = parent[x] = parent[parent[x]];
  return x;
}
function union(a, b){
  a = find(a); b = find(b);
  if(a === b) return;
  if(rank[a] < rank[b]){ const t = a; a = b; b = t; }
  parent[b] = a;
  if(rank[a] === rank[b]) rank[a]++;
}

Path compression (the parent[x] = parent[parent[x]] line) halves the path length on each traversal without a separate flattening pass. After the scan completes, every label is canonicalized by calling find one more time, and cluster sizes are tallied from the canonical labels. The spanning check then looks for any label that appears in both the top row and the bottom row: if one exists, a path connects the two edges, and the medium percolates.

Broadbent's motivating image was a crystal growing inside a porous rock, blocked by the rock's structure from spreading uniformly, hence the name they gave the model in their paper: "percolation processes." The coffee analogy is retroactive and slightly too tidy. What the model actually describes, and what made it immediately useful across disciplines, is any situation where connectivity emerges from local independent decisions. Forest fire spread, epidemic contagion, oil reservoir simulation, polymer gelation, and electrical conductance in composites all exhibit the same qualitative transition: below a threshold, the medium is an insulator or a firebreak; above it, it conducts or burns through. The identity of the threshold differs across models and geometries. The fact that a threshold exists, and that the behavior at criticality has a universal character, is general.

The "Animate p" button in the artifact sweeps the probability slowly from 0 to 1 and back. At p = 0.20 the grid is mostly empty, clusters are tiny, and nothing spans. At p = 0.45 recognizable islands appear, but they stay isolated. The first spanning cluster appears near 0.59, flickering in and out for a few probability steps, then persisting reliably above 0.62. That flicker is not a rendering artifact, it is the genuine behavior of a finite lattice near a continuous phase transition, where fluctuations are large and the system sits at the edge of two stable phases. An infinite lattice would show a sharp step function. A 150×150 grid shows the step rounded by finite-size effects, spread across a probability interval proportional to N^-3/4. The larger the grid, the sharper the transition. The artifact lets you push the grid up to 400×400 to see this directly.

The full interactive version is at the artifact page. The gallery sketch at gallery/percolation runs the same simulation in a stripped frame. Start with Animate p, watch the transition, then push p back to 0.5927 by hand and use Show Spanning to highlight the path — if one exists. At exactly the threshold, it often doesn't. That absence is the point.