A walker starts at the origin of the lattice ℤd and at each step moves to one of its 2d neighbours at random. The origin is recurrent if the walker is sure to come back, and the criterion of Theorem 23.15 says this happens exactly when the expected number of visits, the sum of the return probabilities p00(n), is infinite. Those probabilities decay like n−d/2: the sum diverges on the line and in the plane and converges in space (Pólya's theorem). The gold curves are exact: p00(2k) from counting closed paths, and the first-return probabilities from the renewal equation. The teal curves are what the simulated walkers actually did. A drift on the line makes the walk transient too.
Exact curves. p00(2k) is C(2k, k)(pq)k on the line, [C(2k, k)/4k]2 in the plane, and C(2k, k)ΣjC(k, j)2C(2j, j)/36k in space. The first-return probabilities f solve p00(2k) = Σm≤k f(2m)p00(2k − 2m). Limits (dotted): the probability of ever returning is 1 for d = 1, 2 (symmetric), 1 − |p − q| for the biased walk, and 0.3405 in space; the expected number of returns is then a/(1 − a) with a that probability. One uniform number per step. Random numbers are seeded.
code/ch23_stochastic_processes.py (rw_u, first_return, watson_constant, demo_rw).