Exceptional graphs for the random walk

Abstract

If W is the simple random walk on the square lattice Z², then W induces a random walk W_G on any spanning subgraph G ⊂ Z² of the lattice as follows: viewing W as a uniformly random infinite word on the alphabet {x, −x, y, −y}, the walk W_G starts at the origin and follows the directions specified by W, only accepting steps of W along which the walk W_G does not exit G. For any fixed G ⊂ Z², the walk W_G is distributed as the simple random walk on G, and hence W_G is almost surely recurrent in the sense that W_G 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 W_G is recurrent for every G ⊂ Z²? 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.