Section 16.4

Walks on Cycles and Lattices

The last vertex visited on a cycle, walks on Z^2 and in boxes, squared displacement.

Toolkit

These problems analyse simple random walks on finite graphs (cycles, squares, lattices) using symmetry to reduce states, gambler’s-ruin absorption probabilities, independence of increments, and union-bound counting for self-avoiding paths.

Key tools:

Symmetry reduction: exploit reflections/rotations of the lattice to collapse equivalent states before setting up equations.
Gambler’s ruin: on a path of length $L$ with absorbing ends, hitting probability of one end from position $k$ is $k/L$ ; by symmetry every vertex can be equally likely to be “last” on a cycle.
First-step / hitting-time equations: for expectations or probabilities $f(x)$ on a finite state space, write $f(x)=\frac{1}{\deg x}\sum_{y\sim x} f(y)$ (plus boundary data) and solve the resulting linear system using symmetry classes.
Sum of independent steps: for $D_n=\sum_{i=1}^n X_i$ with i.i.d. mean-zero steps, $\mathbb{E}[D_n^2]=\sum_i \mathbb{E}[X_i^2]$ since cross terms vanish.
Union bound on self-avoiding paths: number of self-avoiding paths of length $n$ from a point is at most $4\cdot3^{n-1}$ on $\mathbb{Z}^2$ ; if each edge is open independently with probability $p$ ,
$\mathbb{P}(\exists \text{ open path of length } n) \le \tfrac{4}{3}(3p)^n,$
giving extinction of long open paths when $3p<1$ .

Problems