The scenery reconstruction problem investigates whether one can identify a coloring of the integers, using only the color record seen along a random walk path. The problem originates from questions by Benjamini, Keane, Kesten, den Hollander, and others.

Specification of the problem

A (one dimensional) scenery is a coloring A of the integers with C colors. Two sceneries are called equivalent if one of them is obtained from the other by a translation or reflection. Let S be a recurrent random walk on the integers. Observing the scenery A along the path of this random walk, one sees the color A(S(t)) at time t. The scenery reconstruction problem is to retrieve the scenery A, given only the sequence of observations A(S(0)),A(S(1)),A(S(2)),....

This problem can also be formulated as follows: Does one path realization of the process A(S(0)),A(S(1)),A(S(2)),... uniquely determine A ?

The answer in those general terms is ``no''. However, under appropriate restrictions, the answer will become ``yes''. Let us explain these restrictions: First, if two sceneries are equivalent, we can in general not distinguish whether the observations come from the first one or the second one. Thus, we can only reconstruct A up to equivalence. Second, the reconstruction works in the best case only almost surely. Eventually, Lindenstrauss in 1999 exhibited sceneries which can not be reconstructed. However, a lot of ``typical'' sceneries can be reconstructed up to equivalence. For this we usually take the scenery A to be the outcome of a random process and prove that almost every scenery can be reconstructed up to equivalence.

Required reading

Kesten wrote a nice overview to scenery reconstruction and distinguishing. Most chapters in my 500 pages-long habilitation are on scenery reconstruction. I recommend our overview paper written jointly with Jyri Lember. Recently I worked with Serguei Popov on continuous sceneries.