Percolation was introduced by Broadbent and Hammersley in 1957. The simplest version to describe is on the Euclidean lattice Zd. Let p be a fixed probability between 0 and 1. Each bond in Zd is retained with probability p, and removed with probability 1-p, independently of all the others. The percolation cluster containing a point x, denoted C(x), consists of those points which can be reached from x by a path of retained bonds. There is a critical value pc∈(0,1) such that if p < pc then all clusters are finite, while for p > pc there is an infinite cluster.
Random walks on percolation clusters were introduced by De Gennes in 1976: he called this the problem of 'the ant in the labyrinth'. If p = p(n,x,y) is the probability that a random walker ('the ant'), starting at x, is at y at time n, then p describes diffusion of heat on the cluster.
For the supercritical phase (p > pc) this problem is now quite well understood, and p(n,x,y) converges to a Gaussian distribution as n→∞. PDE techniques introduced by Nash in the 1950s, play an important role in some of the arguments.
The critical case p = pc is much harder, since the clusters have fractal properties. One expects that p(n,x,x) ∼ x- ds/2, where ds is called the spectral dimension of the cluster. Alexander and Orbach conjectured in 1982 that ds = 4/3 in all dimensions: this has recently been proved in some high dimensional cases.