Source localisation in simple random walks

Abstract

We consider the problem of locating the source (starting vertex) of a simple random walk, given a snapshot of the set of edges (or vertices) visited in the first $n$ steps. Considering lattices ${\mathbb{Z}}^d$, in dimensions $d\ge 5$, we show that the source can be identified (a) with probability bounded away from $0$ using one guess, and (b) with probability arbitrarily close to $1$ using a constant number of guesses. On the other hand, for dimensions $d\le 2$, we show that one cannot locate the source with positive constant probability. Our arguments apply more generally to strongly transient and recurrent simple random walks on vertex-transitive graphs.

25 pages, 1 figure