Information recovery from observations by a random walk having jump distribution with exponential tails

A {\it scenery} is a coloring $ξ$ of the integers. Let $\{S_t\}_{t\geq 0}$ be a recurrent random walk on the integers. Observing the scenery $ξ$ along the path of this random walk, one sees the color $χ_t:=ξ(S_t)$ at time $t$. The {\it scenery reconstruction problem} is concerned with recovering the scenery $ξ$, given only the sequence of observations $χ:=(χ_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.

No reviews yet.

No comments yet.