# SCENERY RECONSTRUCTION

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.