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

Abstract

A {\it scenery} is a coloring $\xi$ of the integers. Let $\{S_t{\}}_{t\ge 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\ge 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.

References in corpus (1)

• Reconstructing a two-color scenery by observing it along a simple random walk path