Information Recovery from Observations by a Random Walk Having Jump Distribution with Exponential Tails

#### A. Hart, F.P. Machado, H. Matzinger

2015, v.21, №4, 939-970

ABSTRACT

A 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.

Keywords: scenery reconstruction, scenery distinguishing, large deviation, random walk