Exceptional graphs for the random walk

摘要

If W is the simple random walk on the square lattice Z(2), then W induces a random walk W-G on any spanning subgraph G subset of Z(2) 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 subset of Z(2), 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 subset of 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.