Each worksheet prints cleanly on A4 or Letter. Answer keys are on a separate page.

The Lumenary · Research pathways

Random structures: walks, percolation and random geometry

Name: ______________________

Date: ______________________

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 — effective resistance, Rayleigh monotonicity and the Nash-Williams inequality — to decide recurrence and transience
Describe the phase transition in bond percolation, prove $\frac13 \le p_c(\Z^2) \le \frac23$ by Peierls' argument, and state Kesten's theorem $p_c = \frac12$
Describe the giant component of the Erdős–Rényi graph $G(n, c/n)$ and its branching-process explanation
Describe Brownian motion and Schramm–Loewner evolution as scaling limits, separating theorems from conjectures and from numerical evidence

1.
How many of the $4^4 = 256$ walks of length $4$ on $\Z^2$ (steps $(\pm1, 0)$ , $(0, \pm 1)$ ) end at the origin?
2.
On which of these graphs is simple random walk recurrent? (Choose all that apply.)
- A. $\Z$
- B. $\Z^2$
- C. $\Z^3$
- D.The binary tree
- E.Any connected subgraph of $\Z^2$ (for example a half-plane)
- F. $\Z^2 \times \{0, 1, 2\}$ , a slab of thickness three
3.
In the rooted binary tree (root of degree $2$ , all other vertices of degree $3$ ), what is the probability that simple random walk started at the root never returns to the root?
- A. $\frac12$
- B. $0$
- C. $\frac13$
- D. $1$
4.
How many edges of $\Z^2$ join a vertex on the boundary of the square $[-2, 2]^2$ to a vertex on the boundary of $[-3, 3]^2$ ? (This is the cutset $\Pi_2$ in the Nash-Williams argument.)
5.
In Peierls' proof that $p_c(\Z^2) \ge \frac13$ , which fact justifies the bound $4 \cdot 3^{n-1}$ on the number of self-avoiding paths of length $n$ from the origin?
- A.Four choices for the first step, and at most three afterwards, because a self-avoiding path never immediately reverses
- B.The connective constant of $\Z^2$ equals $3$
- C.Planar duality
- D.Independence of different edges
6.
In $G(n, c/n)$ with $c = 2$ , roughly what fraction of the vertices lie in the largest component when $n$ is large?
- A.About $0.80$ , the positive root of $\beta = 1 - e^{-2\beta}$
- B.About $0.50$
- C.Essentially all of them
- D.A vanishing fraction, of order log n / n
7.
Which Lean statement says that the expected number of returns to the origin of simple random walk on $\Z$ , $\sum_n \binom{2n}{n}4^{-n}$ , is infinite?
- A.¬ Summable (fun n : ℕ => (centralBinom n : ℝ) / 4 ^ n)
- B.Tendsto (fun n : ℕ => (centralBinom n : ℝ) / 4 ^ n) atTop (𝓝 0)
- C.∀ n, (centralBinom n : ℝ) / 4 ^ n ≤ 1
- D.Summable (fun n : ℕ => ((centralBinom n : ℝ) / 4 ^ n) ^ 3)
8.
Which of these are established theorems (not conjectures or numerical observations)? (Choose all that apply.)
- A.Bond percolation on $\Z^2$ has $p_c = \frac12$ .
- B.The outer boundary of planar Brownian motion has Hausdorff dimension $\frac43$ .
- C.Site percolation on $\Z^2$ has $p_c = 0.5927$ exactly.
- D.For bond percolation on $\Z^3$ , $\theta(p_c) = 0$ .
- E.Critical site percolation on the triangular lattice is conformally invariant in the scaling limit (Cardy's formula holds).
- F.The planar self-avoiding walk converges to SLE(8/3).
9.
Write return_prob_1d(n) returning $P(S_{2n} = 0) = \binom{2n}{n}/4^n$ for simple random walk on $\Z$ as an exact Fraction, return_prob_2d(n) returning the probability for $\Z^2$ (use the rotation trick), and expected_visits(f, N) returning $\sum_{n=0}^{N} f(n)$ . The tests check exact values and the slow growth of the 2D sum.
Computational — Practice
10.
Simple random walk on $\Z$ returns to $0$ with probability $1$ . What is the expected time $E[T]$ of the first return?
- A.Infinite
- B.2
- C.4
- D.It is finite but depends on the starting point

Answer key — Random structures: walks, percolation and random geometry

1.
By the rotation trick, closed walks of length $2n$ on $\Z^2$ correspond to pairs of closed walks of length $2n$ on $\Z$ , so there are $\binom{2n}{n}^2$ of them; for $n = 2$ , $6^2 = 36$ . Directly: a closed walk of length $4$ uses either two steps each way along one axis ( $\frac{4!}{2!\,2!} = 6$ orders, times $2$ axes, giving $12$ ) or one step in each of the four directions ( $4! = 24$ orders): $12 + 24 = 36$ . The first experiment checks the formula by brute force up to length $8$ .
2.
Recurrent: $\Z$ , $\Z^2$ , every connected subgraph of $\Z^2$ (Rayleigh monotonicity), and the slab $\Z^2 \times \{0,1,2\}$ (Nash-Williams with cutsets of size about $24k$ ). Transient: $\Z^3$ (Pólya) and the binary tree (finite resistance $1$ ).
3.
Electrically, the $2^k$ edges between generations $k-1$ and $k$ are in parallel (resistance $2^{-k}$ ) and the generations are in series, so $R_{\mathrm{eff}} = \sum_{k\ge1}2^{-k} = 1$ . By Theorem 3 the escape probability is $\frac{1}{2 \cdot 1} = \frac12$ . Check: from a child, the probability $h$ of ever hitting its parent solves $h = \frac13 + \frac23h^2$ , so $h = \frac12$ ; the walk from the root returns iff it comes back from its first step, with probability $\frac12$ .
4.
Each of the four sides of $[-2, 2]^2$ has $2k + 1 = 5$ vertices, each with exactly one edge pointing outwards, so $|\Pi_2| = 4 \cdot 5 = 20 = 8 \cdot 2 + 4$ . The Nash-Williams bound $R_{\mathrm{eff}} \ge \sum_k \frac{1}{8k+4} = \infty$ proves recurrence of $\Z^2$ .
5.
A self-avoiding path cannot revisit the vertex it just left, so after the first step (4 choices) each step has at most 3 choices: at most $4 \cdot 3^{n-1}$ paths. With the union bound, $\theta(p) \le 4\cdot3^{n-1}p^n \to 0$ when $p \lt \frac13$ (Lean: peierls_tendsto).
6.
Exploring a component is approximately a branching process with Poisson( $2$ ) offspring. Its survival probability is the positive root of $\beta = 1 - e^{-2\beta}$ , $\beta \approx 0.797$ , and by the Erdős–Rényi theorem the giant component has $(\beta + o(1))n$ vertices w.h.p. The second experiment finds about $0.79$ – $0.80$ with $n = 2000$ .
7.
¬ Summable (fun n : ℕ => (centralBinom n : ℝ) / 4 ^ n) is the statement; in Lean it is proved by comparison with ∑ 1/(2n+1), using Mathlib's 4ⁿ ≤ (2n+1) C(2n, n). The other options are true but different: the terms tend to 0, are at most 1, and their cubes are summable.
8.
Theorems: Kesten's $p_c = \frac12$ , the Lawler–Schramm–Werner proof of the $\frac43$ conjecture, and Smirnov's conformal invariance for triangular-lattice site percolation. Not theorems: the value $0.5927$ (numerical), $\theta(p_c) = 0$ on $\Z^3$ (open), and the $\mathrm{SLE}_{8/3}$ limit of self-avoiding walk (open).
9.
```
from fractions import Fraction
from math import comb


def return_prob_1d(n):
    return Fraction(comb(2 * n, n), 4 ** n)


def return_prob_2d(n):
    return return_prob_1d(n) ** 2


def expected_visits(f, N):
    return sum(f(n) for n in range(N + 1))
```
The 2D sum grows like $\frac{1}{\pi}\log N$ : from $N = 100$ to $N = 400$ it increases by about $\frac{\log 4}{\pi} \approx 0.44$ . It diverges — the walk is recurrent — but so slowly that no simulation could convince you of it; the proof (in the lesson and in Lean) can.
10.
$E[T] = \sum_k P(T \gt k) = 2\sum_n P(T \gt 2n) = 2\sum_n u_{2n}$ , using the identity $P(T \gt 2n) = u_{2n}$ for the walk on $\Z$ . This is exactly the divergent series of Pólya's theorem (return_1d_not_summable in Lean). So $T$ is finite almost surely but $E[T] = \infty$ — 'null recurrence'.