Percolation

The Percolation Problem

Percolation is a model used to study a wide range of physical systems, from the flow of liquids through porous materials to the connectivity of electrical grids. We model the system using an n-by-n grid of sites, where each site is either open or blocked.

A system percolates if there is a path of connected open sites from the top row to the bottom row. The central question is: if sites are opened randomly with probability p, what is the percolation threshold p* at which the system is likely to percolate?

The Percolation Data Type

To model this system, we create a Percolation data type with the following API:

public class Percolation {
    // Creates an n-by-n grid, with all sites initially blocked
    public Percolation(int n)

    // Opens the site (row, col) if it is not open already
    public void open(int row, int col)

    // Is the site (row, col) open?
    public boolean isOpen(int row, int col)

    // Is the site (row, col) full (connected to the top)?
    public boolean isFull(int row, int col)

    // Returns the number of open sites
    public int numberOfOpenSites()

    // Does the system percolate?
    public boolean percolates()
}

Implementation Notes

• The grid is mapped to a 1D array to be used with the WeightedQuickUnionUF data structure.
• Two virtual sites (top and bottom) are used to efficiently check for percolation. A second WeightedQuickUnionUF instance without a virtual bottom site is used to prevent the “backwash” problem when checking if a site is full.

Monte Carlo Simulation

Since a mathematical solution for p* is unknown, we estimate it using a Monte Carlo simulation:

1. Initialize an n-by-n grid with all sites blocked.
2. Repeatedly open a random blocked site.
3. Stop when the system percolates.
4. The fraction of open sites (opened_sites / (n*n)) is an estimate of p*.

The PercolationStats Data Type

To get a more accurate estimate, we run the experiment multiple times and analyze the results. The PercolationStats data type automates this process.

public class PercolationStats {
    // Perform independent trials on an n-by-n grid
    public PercolationStats(int n, int trials)

    // Sample mean of the percolation threshold
    public double mean()

    // Sample standard deviation of the percolation threshold
    public double stddev()

    // Low endpoint of the 95% confidence interval
    public double confidenceLo()

    // High endpoint of the 95% confidence interval
    public double confidenceHi()
}

By running a large number of trials, we can calculate the mean, standard deviation, and a 95% confidence interval for the percolation threshold p*.