Information Recovery from Observations by a Random Walk Having Jump Distribution with Exponential Tails
A. Hart, F.P. Machado, H. Matzinger
2015, v.21, Issue 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
COMMENTS
Please log in or register to leave a comment