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

MaRDI QIDQ2811804zbMATH OpenFDO

Authors Fábio P. Machado, A. Hart, Heinrich Matzinger

Publication date 10 June 2016

Published in Markov Processes and Related Fields (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.6853, http://math-mprf.org/journal/articles/id1400/

zbMATH Keywords

random walklarge deviationsscenery reconstructionscenery distinguishing

Mathematics Subject Classification ID

Large deviations (60F10) Sums of independent random variables; random walks (60G50) Processes in random environments (60K37)

Abstract: A {it scenery} is a coloring $xi$ of the integers. Let ${S_t}_{tgeq0}$ be a recurrent random walk on the integers. Observing the scenery $xi$ along the path of this random walk, one sees the color $ch{i}_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:=(ch{i}_t{)}_{tgeq0}$. 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.

Recommendations

• Reconstructing a piece of scenery with polynomially many observations.
• Scenery reconstruction
• Reconstructing a random scenery observed with random errors along a random walk path
• Reconstructing a multicolor random scenery seen along a random walk path with bounded jumps
• Reconstruction of periodic sceneries seen along a random walk

Cited in

(3)

• Scenery reconstruction for random walk on random scenery systems
• Lower bounds for trace reconstruction
• Reconstructing a piece of scenery with polynomially many observations.

This page was built for publication: Information recovery from observations by a random walk having jump distribution with exponential tails

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811804)