Exceptional graphs for the random walk

Journal article

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.

Authors: Aru, J; Groenland, C; Johnston, T; Narayanan, B; Roberts, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Institute Henri Poincaré
• Journal: Annales de l'Institut Henri Poincaré (B) Probabilités et Statistiques
• Volume: 56
• Issue: 3
• Pages: 2017-2027
• Publication date: 2020-06-26
• Acceptance date: 2019-09-28
• DOI: 10.1214/19-AIHP1026
• ISSN: 0246-0203
• Language: English
• Keywords: FFR; recurrence and transience; random walks; exceptional graphs; traversal sequences