Site Percolation

DEFINITION

each site open with probability p, independently
clusters = connected components of open sites, 4-neighbour
labels merged by union-find; the larger label survives a merge
spanning ⇔ one cluster touches both the top and the bottom row
p_c = 0.59274621(13) for sites on the square lattice

NOTES

Open each site of a square grid with probability p, independently, and ask whether the open sites connect the top edge to the bottom. Below one critical value of p they essentially never do: the picture is dust, hundreds of small clusters, and the largest of them is a speck. Above it they essentially always do, and the picture is one block with holes in it. Between those two descriptions sits a single value of p, and the cluster that appears there is neither dust nor block — it spans the frame, and its arms are ramified at every scale down to the lattice, with fractal dimension 91/48 rather than the 2 a solid region would have. Fractal exactly at threshold, boring either side: that is what a phase transition looks like when you can watch it happen. The number is 0.59274621 for sites on the square lattice and no closed form for it is known, which is worth holding next to the fact that the bond version of the same question on the same lattice is exactly one half and was proved so. The sweep here fixes a random arrival order for every site once, so raising p is only ever opening the next site in that order, and one pass covers the whole range instead of one lattice per value. When the top and the bottom finally share a cluster the plate says so, and colours that cluster apart from every other.

PROVENANCE

Origin

S. R. Broadbent & J. M. Hammersley, "Percolation processes I. Crystals and mazes", Mathematical Proceedings of the Cambridge Philosophical Society 53(3), 1957, 629–641 (doi:10.1017/S0305004100032680). The paper that asked the question in the form this plate draws: a fluid entering a random medium, and whether it reaches the far side. Broadbent was working on gas masks, which is where the random medium came from.

The labelling

J. Hoshen & R. Kopelman, "Percolation and cluster distribution. I. Cluster multiple labeling technique and critical concentration algorithm", Physical Review B 14(8), 1976, 3438–3445 — the src link above, and the algorithm that decides what colour every cell here is. Their contribution is that a cluster does not need a search: give each site a provisional label, and keep a second array in which a label points at the label it turned out to be the same as, so two provisional labels meeting is one write rather than a relabelling of everything behind them. That second array is a disjoint-set forest, and the chase up it to the proper label is a find. Implemented here from the technique, not from any listing of it.

The sweep in one pass

M. E. J. Newman & R. M. Ziff, "Efficient Monte Carlo algorithm and high-precision results for percolation", Physical Review Letters 85(19), 2000, 4104–4107 (doi:10.1103/PhysRevLett.85.4104). Two things come from here. The first is the observation this plate is built on: fix one random arrival order for the sites and open them along it, and every value of p from 0 to 1 is visited in a single monotone pass, because raising p can only ever add a site and adding a site can only ever merge clusters. Sweeping p the naive way is one independent lattice per value and no continuity between frames at all. The second is the modern figure — their abstract states the transition at 0.59274621(13) for site percolation on the square lattice, and that is the number quoted on this plate.

Why there is no exact value

For BOND percolation on the same square lattice the threshold is exactly one half, proved: H. Kesten, "The critical probability of bond percolation on the square lattice equals 1/2", Communications in Mathematical Physics 74(1), 1980, 41–59 (doi:10.1007/BF01197577). The proof leans on the square bond lattice being self-dual, and the site problem has no such symmetry to lean on — its matching lattice is the square lattice with diagonals, a different lattice. So the site threshold is a measured number and not a derived one, which is why every digit past the fifth is somebody having run the computation.

Standing

Public domain — a probability, a connectivity rule, and a disjoint-set forest. Nothing here is taken from any percolation library, sketch or listing; the labelling is written from the technique the 1976 paper sets out and the arrival-order sweep from the observation the 2000 paper makes.

Checked, not just plotted

Three independent numbers, 400 runs at each of five lattice sizes, all measured on this implementation before the ranges below were declared. FIRST, the threshold. The mean p at which the plate fires its spanning event is 0.59348 / 0.59271 / 0.59330 / 0.59292 / 0.59275 at L = 80 / 100 / 140 / 200 / 260, against standard errors of 0.00098 / 0.00081 / 0.00061 / 0.00048 / 0.00039. The published value is 0.59274621(13), and every one of the five sits inside one standard error of it; at L = 260 the mean lands on it to five decimal places. Nothing in the code above was fitted to that number, which is the whole point of quoting it. SECOND, the exponent. The spread of the spanning threshold is not noise to be averaged away, it is finite-size scaling: the correlation length exponent for two-dimensional percolation is nu = 4/3, so the width should fall as L to the minus 3/4. Measured, sd times L^0.75 is 0.5233 / 0.5125 / 0.4958 / 0.5104 / 0.5042 across those five sizes — flat to within three percent over a factor of three in L, which is the exponent showing up in the plate rather than being asserted on it. THIRD, the dimension. The caption claims fractal dimension 91/48 at threshold, so the mass of the spanning cluster at the instant it appears should go as L to the 91/48. Measured, mass divided by L^(91/48) is 0.5190 / 0.5041 / 0.5001 / 0.5012 / 0.5064 — flat to two percent past the smallest lattice, where a solid region would instead have given a number rising as L to the 5/48 and a simple path one falling far faster.

What the colours are doing

Every finite cluster is coloured by a hash of its own label, and the hash lands in the ramp bright lobe only — 0.74 to 1.26, which wraps through the peak and stops well short of the trough at 0.5. A label falling in the trough would render an entire cluster blacker than the ink, and which clusters those were would depend on the permutation, so the plate would be legible or not depending on the seed. That is the defect ising shipped with, in a different costume. The spanning cluster is not given a hash: it takes the ramp peak lifted 55 percent of the way to white, so it is the one desaturated thing on the plate and reads apart from the whole family of finite-cluster colours at any accent. It is deliberately not HILITE itself. Measured over 400 runs at L = 140, the spanning cluster at the instant it appears is a median 0.51 of the open sites with a tenth to ninetieth percentile of 0.29 to 0.73 and a maximum of 0.90 — so in the tail a flat white would be more than half the frame, and the fill past threshold takes it higher still. That spread is worth reading rather than averaging: at the low end the thing that first crosses the frame is a wisp, and being able to see a wisp is the reason it is coloured apart at all.

The merge keeps the picture still

Union by size is normally just a bound on the tree depth. It is doing a second job here worth naming: the surviving label after a merge is the LARGER cluster, so when two clusters join the big one keeps its colour and only the small one is recoloured. With union by rank, or with no rule at all, roughly half of all merges would repaint the larger region and the plate would flicker its way to threshold. What that argument does NOT license is caching the spanning cluster by its label, and the draw deliberately does not: a label is only the current representative of a cluster and any later merge can retire one. Measured, the spanning cluster is the largest on the lattice in 97 to 99 percent of runs, so a cached label would be right almost always and would silently move the spanning colour onto some other region of the plate in the rest. The site that caused the transition is remembered instead and its label resolved afresh each paint, which is one find and always correct.

Cost

Measured on a 900 px canvas, steady-state mean and p95 milliseconds a paint: 0.17 and 0.27 at the 80 lattice, 0.51 and 0.65 at the default 140, 1.05 and 1.36 at 200, 1.76 and 2.28 at the 260 ceiling. That is a label resolve and a colour write for every cell plus pixels(), and it is inside the budget everywhere in the declared range. The one-off at the head of a run is the Fisher-Yates permutation and the arrays around it, and it does not show above the noise of an ordinary paint even at the ceiling — measured, the first frame of a run costs less than the steady state at 140 and at 260, because it shades a nearly empty lattice. So there is nothing here to spread across frames: Gray-Scott earned that rule at 125 to 326 ms and mazlack declined it at 4.9 ms once every 201 frames, and this is smaller than either.

Constants

cells is locked from regenerate for cost and for finite size, per taxonomy.js. rate is the sweep speed written as a change in p per frame rather than as sites per frame, so it does not silently mean something different on a different lattice — at the default the plate takes about 200 frames to reach threshold and about five seconds to complete a cycle, and every value in range renders. beyond is how far past the spanning point the fill continues before the picture is held and a fresh permutation starts: it is what shows the supercritical half of the caption, the spanning cluster swallowing everything left. Liveness, tested the way regenerate actually jitters — 240 random tuples of rate and beyond across 8 seeds — is 240 of 240 live, with the spanning event reached in every one. Measured a second way, one whole cycle counted from a restart at each corner of the declared box: the default cycle is 345 frames with not one frame under the visibility rule, and the only corner that has any is the smallest lattice at the slowest rate, where 4 frames of a 779 frame cycle sample as flat ink because 6 sites of 6,400 have been opened. That corner is unreachable from regenerate, since cells is locked, and it lasts 67 milliseconds; it is on the record rather than tuned away, because the honest description of those four frames is that almost nothing is open yet.

Source

doi:10.1103/PhysRevB.14.3438