Phys 1379 · Machine Learning in the Sciences · demo
Percolation
Fill a grid at random and ask a simple question: is there a connected path from top to bottom? The answer changes abruptly at one special density, the simplest example of a phase transition.
1The model
Take an \(L \times L\) square grid and occupy each site independently with probability \(p\). Two occupied sites belong to the same cluster if they are neighbours (up, down, left or right), and clusters are built up by following neighbours. The grid percolates if one cluster touches both the top row and the bottom row.
Think of water seeping through porous rock, a fire spreading through a forest, or current flowing through a mixture of metal and insulating grains. At low \(p\) the clusters are small and isolated; at high \(p\) almost everything is connected. The interesting question is what happens in between.
2A sharp threshold
For a very large grid the change is abrupt. There is a critical density \(p_c\) below which the chance of a spanning cluster is zero and above which it is one. For sites on the square lattice no formula for \(p_c\) is known; simulations give
This is a phase transition, of the same kind as a magnet losing its magnetisation when heated, and it is studied with the same tools. Near \(p_c\) there are clusters of every size, and the largest ones are fractals.
A finite grid cannot be perfectly sharp. The spanning probability \(P(p)\) rises smoothly from 0 to 1 over a window around \(p_c\) whose width shrinks as the grid grows,
So the curve for a 200 × 200 grid is much steeper than for a 25 × 25 grid, and in the limit \(L\to\infty\) it becomes a step at \(p_c\).
3How the simulation works
For each value of \(p\), the program makes \(N\) random grids. In each one it labels the clusters and checks whether any label appears in both the top and the bottom row. The fraction of grids that percolate estimates \(P(p)\).
The error bar comes from the bootstrap: draw \(N\) results at random, with replacement, from the \(N\) actual results, recompute the fraction, repeat 1000 times, and take the standard deviation of the 1000 fractions. For a fraction this is close to the familiar binomial error,
The bootstrap needs no such formula, which is why it is used throughout data analysis and machine learning.
4Try it
Move the slider to see a single grid fill up: the same random numbers are kept, so raising \(p\) only adds sites and you can watch clusters merge. Each cluster has its own colour; a spanning cluster is drawn in black (white on a dark screen). Run sweeps \(p\) from 0.30 to 0.80 as in the course code, with extra points near \(p_c\); press it again to stop.
Things to try
- Set the slider to 0.50, then 0.59, then 0.65. Below \(p_c\) the clusters are small; at \(p_c\) there are clusters of every size; above it one giant cluster takes over.
- Run with \(L = 25\), then with \(L = 100\), without clearing. Finished curves stay on the plot: the larger grid gives a steeper curve, Eq. \eqref{eq:width}, and the curves cross close to \(p_c\).
- Increase \(N\): the error bars shrink like \(1/\sqrt N\), Eq. \eqref{eq:err}, and the run takes longer.
- Choose Slow to watch each grid as it is tested.
5Code and references
- The course code,
percolationAnim.py(numpy, scipy, matplotlib; clusters labelled withscipy.ndimage.label). This page re-implements it in JavaScript with the same \(p\) values, grid test and bootstrap; it adds the single-grid slider, keeps finished curves for comparison, and marks \(p_c\) on the plot. - D. Stauffer and A. Aharony, Introduction to Percolation Theory, 2nd ed. (Taylor & Francis, 1994).
- M. E. J. Newman and R. M. Ziff, "Efficient Monte Carlo algorithm and high-precision results for percolation", Phys. Rev. Lett. 85, 4104 (2000), cond-mat/0005264: the value of \(p_c\) in Eq. \eqref{eq:pc}.