ABSTRACT

SCENERY RECONSTRUCTION IN TWO COLORS WITH JUMPS

Henry Matzinger, December 12, 2001

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. During the last years, several people at Eurandom worked on solving several different versions of this problem. A (one dimensional) scenery is a coloring $\xi $ of the integers $\QTR{Bbb}{Z}$ with $C_{0}$ colors $\{1,\ldots ,C_{0}\}$. Two sceneries are called equivalent if one of them is obtained from the other by a translation or reflection. Let $(S(t))_{t\geq 0}$ be a recurrent random walk on the integers. Observing the scenery $\xi $ along the path of this random walk, one sees the color $\chi (t):=\xi (S(t))$ at time $t$. The \QTR{it}{scenery reconstruction problem} is to retrieve the scenery $\xi $, given only the sequence of observations $\chi $. Quite obviously retrieving a scenery can only work up to equivalence.

Back to the history of the seminar or the Colloquium Stochastiek homepage.

Martijn Pistorius (pistorius@math.uu.nl)

Last Updated: December 12, 2001