2.4 A Case Study: Percolation

This section is under construction.

Data representation.

Program BooleanMatrix.java is a library of static methods for manipulating boolean matrices.

Data visualization.

Program Visualize.java is a test client that generates random boolean matrices and plots them using standard draw.

Downward percolation.

Program PercolationDown.java solves the somewhat easier problem of determining whether there is a path from the top to the bottom that only goes down the grid.

Estimating probabilities.

Program Estimate.java generates many N-by-N systems and computes the fraction that percolate.

Adaptive plot.

Program PercPlot.java plots the fraction of N-by-N systems that percolate given that each site is blocked with probability p.

Depth first search solution.

Program Percolation.java handles the general case using depth first search.

Lessons

Q + A

Q. What is the percolation threshold for different lattices?

A. As N gets large, there is a percolation threshold probability p* such that if p < p* then no spanning cluster exists, and if p >= p* then one spanning cluster exists.

Q. Any relevant papers?

A. Any relevant papers? Here's a recent physics paper that uses this technique.

Exercises

2-by-2 percolation. Verify that the probability that a 2-by-2 system percolates is p^2 (2 - p^2), where p is the probability that a site is open.
Bond percolation. Each edge is open/blocked with probabilit p (instead of each vertex). Compute percolation threshold for N-by-N square lattice. (Analytic solution = 1/2). Repeat for cube lattice (no analytic solution known).
Cubic curves. Use recursive subdivision algorithm to plot cubic curves.
Random walk. Term coined by Hungarian mathematician George Polya in a 1921 paper. Start at 0, go left with probability 1/2, go right with probability 1/2. Reflecting barrier at 0 - if particle hits 0, it must switch direction at next step and return to 1. Absorbing barrier at N - particle stops when it hits state N. Estimate number of steps as a function of N until the particle is absorbed.
Analytical solution: N².
3d random walk. Take a random walk on a 3d lattice, starting from (0, 0, 0). Write a program Polya.java to estimate the chance that you return to the origin after at most some number of steps, say 1,000. (In 1d and 2d, you will surely return; in 3d, there is a less than 50% chance.) Repeat the exercise on a 4d lattice. Solution: the actual probability (without the artificial restriction on the number of steps) is known as Polya's random walk constant. It is slightly more than 1/3 for 3D and slightly less than 1/5 for 4D.
Self-avoiding random walk. Simulate random walk on lattice until it intersects. Among all self-avoiding walks (SAW) of length N, what is average distance from origin? To save time in the simulation, exclude SAWs that ever take a step backwards. How long until at least one SAW of length N = 40, N = 80? What is half-life of a SAW? To save more time in the simulation, allow a SAW only to take a step into an unoccupied cell (and repeat until it gets trapped). Practically nothing is known rigorously about these questions, so simulation is the best recourse. Here's an article from the New Scientist.
Famous 1949 problem of Nobel prize winning chemist, Flory. Conjecture: exponent of root mean square displacement is 3/4 in 2D and 3/5 in 3D.
Self-avoiding random walk. Write a program SelfAvoidingWalk.java to simulate and animate a 2D self-avoiding random walk. Self-avoiding random walks arise in modeling physical processes like the folding of polymer molecules. Such walks are difficult to model using classical mathematics. so they are best studied by direct numerical simulation. See what fraction of such random walks end up more than R^2 (say 30) from the starting point.
Or keep a trail of length N.