A { \it scenery} is a coloring $\xi$ of the integers. 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 { \it scenery reconstruction problem} is concerned with recovering the scenery $\xi$, given only the sequence of observations $\chi:=(\chi_t)_{ t\geq 0}$. The scenery reconstruction methods presented to date require the random walk to have bounded increments. Here, we present a new approach for random walks with unbounded increments which works when the tail of the increment distribution decays exponentially fast enough and the scenery has five colors.
Categories: math.PR