Detecting defects in periodic scenery by random walks on Z

Thinking of a deterministic function s: Z → N as “scenery” on the integers, a random walk (Z₀, Z₁, Z₂,…) on Z generates a random record of scenery “observed” along the walk: s(Z) = (s(Z₀), s(Z₁),…). Suppose t: Z → N is another scenery on the integers that is neither a translate of s nor a translate of the reflection of s. It has been conjectured that, under these circumstances, with a simple symmetric walk Z the distributions of s(Z) and t(Z) are orthogonal. The conjecture is generally known to hold for periodic s and t. In this paper we show that the conjecture continues to hold for periodic sceneries that have been altered at finitely many locations with any symmetric walk whose steps are restricted to {−1, 0, +1}. If both sceneries are purely periodic and the walk is asymmetric (with steps restricted to {−1, 0, +1}), we get a somewhat stronger result. © 1996 John Wiley & Sons, Inc.