Distinguishing sceneries by observing the scenery along a random walk path

LetG be an infinite connected graph with vertex setV. Ascenery onG is a map ξ :V → 0, 1 (equivalently, an assignment of zeroes and ones to the vertices ofG). LetS _{n n≥0} be a simple random walk onG, starting at some distinguished vertex v₀. Now let ξ and η be twoknown sceneries and assume that we observe one of the two sequences ξ(S _n) _n≥0 or {η(S _n)} _n≥0 but we do not know which of the two sequences is observed. Can we decide, with a zero probability of error, which of the two sequences is observed? We show that ifG = Z orG = Z², then the answer is “yes” for each fixed ξ and “almost all” η. We also give some examples of graphsG for which almost all pairs (ξ, η) are not distinguishable, and discuss some variants of this problem.