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.