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

zbMATH Open1342.60065arXiv1110.6853MaRDI QIDQ2811804FDOQ2811804

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

Publication date: 10 June 2016

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

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.

Full work available at URL: https://arxiv.org/abs/1110.6853

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

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)

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)