Reconstructing a random scenery observed with random errors along a random walk path (Q1396756)

The authors study the scenery reconstruction problem. They show that a random walker can reconstruct the colored scenery it has walked through, even if the walker makes a few mistakes. The scenery consists of a number of colors larger than the number of possible jumps the walker can make. The scenery is symmetric i.i.d., the errors are stationary and ergodic and independent of the random walk, which is supposed only to be recurrent and have bounded jumps. The authors prove that under these conditions almost all sceneries can almost surely be reconstructed.