Reconstruction of random sceneries (Q5945154)

This is a nice survey on the problem of distinguishing/reconstructing a random scenery based on the observations along the path of a random walk. A simple setting is the following: assign to all points of the lattice colours from a finite set. This colouring is called a scenery on the lattice. Run a simple random walk on the lattice. Given as observations the sequence of colours the random walk meets (but not its locations!), is it possible to distinguish two (known) sceneries? Or is it even possible to reconstruct an (unknown) scenery from these observations? An example of a result on the first question is that almost surely, two i.i.d. sceneries can be distinguished by the observations along a simple random walk. The author gives some background and reviews recent results on the topic (among them, extensions to non-nearest-neighbour random walks) and illustrates some of the ideas of the proofs. He also mentions the related problem of random coin tossing.