Random structures: walks, percolation and random geometry

Builds on

Required prerequisites, all the way down: 53

You will learn to

• Prove Pólya's theorem that simple random walk is recurrent in dimensions 1 and 2 and transient in dimensions 3 and higher.
• Use electrical networks to decide recurrence and transience of random walks on graphs.
• Describe the phase transition in bond percolation, prove that the critical probability on ℤ² is strictly between 0 and 1, and state Kesten's theorem p_c = 1/2.

Definition

• A random walk is recurrent if it returns to its starting point with probability 1, and transient otherwise.
• In bond percolation on a graph each edge is open independently with probability p; the critical probability p_c is the infimum of p for which an infinite open cluster exists with positive probability.
• The Erdős–Rényi random graph G(n, p) has n vertices, with each possible edge present independently with probability p.

Theorem

• Pólya (1921): simple random walk on ℤᵈ is recurrent for d ≤ 2 and transient for d ≥ 3.
• Kesten (1980): the critical probability for bond percolation on ℤ² is 1/2.
• Erdős–Rényi: G(n, c/n) has a giant component of linear size with high probability when c > 1, and only small components when c < 1.
• Brownian paths in the plane have Hausdorff dimension 2, and their outer boundary has dimension 4/3 (Lawler–Schramm–Werner).

Common misconceptions

• Thinking a recurrent walk must return quickly; in dimension 1 and 2 the expected return time is infinite.
• Believing simulations near a critical point determine the critical exponents exactly; they give estimates, while exact values need proofs such as those using SLE.

Optional discoveries

• Geometric group theory Random walks on Cayley graphs detect amenability and growth, linking probability to the geometry of groups.
• Fourier and harmonic analysis Harmonic functions are exactly those whose value is the average over a random walk step; on ℝⁿ, Brownian motion connects probability to the Laplace equation.
• ← Markov chains
• ← Geometric group theory

Further reading

• Russell Lyons and Yuval Peres, Probability on Trees and Networks (2016)
• Geoffrey Grimmett, Percolation (1999)