What this shows
The grid is a square lattice of sites. Sites open one at a time, in a random order, until every site is open. Open sites that touch along an edge (up, down, left or right, not diagonally) belong to the same cluster, and each cluster gets its own color.
The fraction of open sites is the occupation probability p, shown in the corner. At first the clusters are small and scattered. Then, in a short window of p, they merge rapidly, and one cluster connects the top row to the bottom row: it spans the grid. From then on the spanning cluster stays bright and the others are dimmed, and the corner also shows the value of p at which the first spanning cluster appeared.
How the visualization works
- Each step opens one closed site chosen uniformly at random, using a seeded pseudo-random generator. The same seed and grid size always open the same sites in the same order, so a shared link replays the same sweep.
- Clusters are tracked as the sweep runs. When a new site joins two clusters, every site of the smaller one is relabeled into the larger. Each site can be relabeled at most about log₂ N times, because its cluster at least doubles every time, so a whole sweep of N sites stays fast.
- This sweep is the idea behind the Newman–Ziff algorithm: a single run passes through every value of p from 0 to 1, instead of building a separate random grid for each p.
- The simulation runs in a Web Worker, off the main thread, and sends the current grid to the page for drawing.
Parameters
- Grid size: sites along each side of the square. Changing it restarts the sweep from the seed.
- Sweep time: how many seconds it takes to open every site. Applies immediately.
Mathematical background
In site percolation, each site of an infinite lattice is open independently with probability p. Percolation theory asks when the open sites form an infinite connected cluster. There is a sharp critical probability pc: below it, every cluster is finite; above it, an infinite cluster exists. Both statements hold with probability one. It is one of the simplest models with a phase transition.
For site percolation on the square lattice, no exact formula for pc is known. Newman and Ziff estimated it numerically as pc = 0.59274621(13), with the uncertainty in the last two digits.
A finite grid has no infinite cluster, so "spans top to bottom" stands in for it. On a finite grid the first spanning happens at a slightly different p in each run, scattered around pc. The scatter shrinks as the grid gets larger, so try a few seeds at a small grid size and then at a large one.
The sweep opens an exact number of sites, while the textbook model opens each site independently. After k steps, every set of k open sites is equally likely. For large grids this behaves like independent opening with p = k / N, and Newman and Ziff show how to convert results between the two exactly.
References
Broadbent and Hammersley introduced percolation in 1957. The sweep and the numerical value of pc come from Newman and Ziff (2000). Full citations are listed below.
- S. R. Broadbent and J. M. Hammersley. Percolation processes (1957). Mathematical Proceedings of the Cambridge Philosophical Society 53(3), 629–641. The paper that introduced percolation theory.
- M. E. J. Newman and R. M. Ziff. Efficient Monte Carlo Algorithm and High-Precision Results for Percolation (2000). Physical Review Letters 85, 4104. The sweep algorithm used here, and the estimate p_c = 0.59274621(13) for square-lattice site percolation.