Exceptional graphs for the random walk

Juhan Aru, Carla Groenland, Tom Johnston, Bhargav Narayanan, Alex Roberts, Alex Scott

Research output: Contribution to journalArticlepeer-review


If W is the simple random walk on the square lattice Z2, then W induces a random walk WG on any spanning subgraph G ⊂ Z2 of the lattice as follows: viewing W as a uniformly random infinite word on the alphabet {x, −x, y, −y}, the walk WG starts at the origin and follows the directions specified by W, only accepting steps of W along which the walk WG does not exit G. For any fixed G ⊂ Z2, the walk WG is distributed as the simple random walk on G, and hence WG is almost surely recurrent in the sense that WG visits every site reachable from the origin in G infinitely often. This fact naturally leads us to ask the following: does W almost surely have the property that WG is recurrent for every G ⊂ Z2? 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.

Original languageEnglish (US)
Pages (from-to)2017-2027
Number of pages11
JournalAnnales de l'institut Henri Poincare (B) Probability and Statistics
Issue number3
StatePublished - Aug 2020

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


  • Exceptional graphs
  • Random walks
  • Recurrence and transience
  • Traversal sequences


Dive into the research topics of 'Exceptional graphs for the random walk'. Together they form a unique fingerprint.

Cite this