Recurrence and capacity of graphs

Remarks

For a finite network, the probability that the walk from $a$ reaches $b$ before returning to $a$ is $1/\big(c(a) R_{\mathrm{eff}}(a, b)\big)$. This follows from the fact that $x \mapsto \mathbb{P}_x[\text{hit } b \text{ before } a]$ is harmonic off $\set{a, b}$, so it is $1 - v$ for the voltage $v$ with $v(a) = 1$ and $v(b) = 0$. The statement follows by applying this to $G_n$ and letting $n \to \infty$. The limit increases because $G_{n+1}$ arises from $G_n$ by un-gluing vertices, which raises resistance by the Rayleigh monotonicity law. Example: on $\Z^2$ with unit conductances, the edges between the boundary of the box $[-k, k]^2$ and the next box form $4(2k + 1)$ disjoint cutsets. The Nash-Williams inequality gives $R(0 \leftrightarrow \infty) \ge \sum_{k \ge 0} \frac{1}{4(2k + 1)} = \infty$, so the simple random walk on $\Z^2$ is recurrent. On $\Z^3$ the resistance to infinity is finite, which gives the transience part of Pólya's recurrence theorem.

Going deeper

For a student

The theorem lets one decide recurrence with the tools of electrical networks. Lower bounds on resistance come from gluing vertices, as in the Nash-Williams inequality; upper bounds come from flows of finite energy, by Thomson's principle. Recurrence is a property of the graph and the conductances, not of the starting vertex. Indeed $R(a \leftrightarrow \infty)$ is finite for one vertex exactly when it is finite for all vertices of the connected graph. Comparisons between graphs, for example under bounded changes of conductances, preserve recurrence and transience.