Exceptional graphs for the random walk

Abstract

If $\mathcal{W}$ is the simple random walk on the square lattice ${\mathbb{Z}}^2$, then $\mathcal{W}$ induces a random walk ${\mathcal{W}}_G$ on any spanning subgraph $G\subset {\mathbb{Z}}^2$ of the lattice as follows: viewing $\mathcal{W}$ as a uniformly random infinite word on the alphabet $\{\mathbf{x},-\mathbf{x},\mathbf{y},-\mathbf{y}\}$, the walk ${\mathcal{W}}_G$ starts at the origin and follows the directions specified by $\mathcal{W}$, only accepting steps of $\mathcal{W}$ along which the walk ${\mathcal{W}}_G$ does not exit $G$. For any fixed subgraph $G\subset {\mathbb{Z}}^2$, the walk ${\mathcal{W}}_G$ is distributed as the simple random walk on $G$, and hence ${\mathcal{W}}_G$ is almost surely recurrent in the sense that ${\mathcal{W}}_G$ visits every site reachable from the origin in $G$ infinitely often. This fact naturally leads us to ask the following: does $\mathcal{W}$ almost surely have the property that ${\mathcal{W}}_G$ is recurrent for \emph{every} subgraph $G\subset {\mathbb{Z}}^2$? We answer this question negatively, demonstrating that exceptional subgraphs exist almost surely. In fact, we show more to be true: exceptional subgraphs continue to exist almost surely for a countable collection of independent simple random walks, but on the other hand, there are almost surely no exceptional subgraphs for a branching random walk.

19 pages, submitted