Reconstructing a piece of scenery with polynomially many observations

Heinrich Matzinger and Silke W. W. Rolles

Stochastic Processes and their Applications, 2003, vol. 107, issue 2, 289-300

Abstract: Benjamini asked whether the scenery reconstruction problem can be solved using only polynomially many observations. In this article, we answer his question in the affirmative for an i.i.d. uniformly colored scenery on observed along a random walk path with bounded jumps. We assume the random walk is recurrent, can reach every integer with positive probability, and the number of possible single steps for the random walk exceeds the number of colors. For infinitely many l, we prove that a finite piece of scenery of length l around the origin can be reconstructed up to reflection and a small translation from the first p(l) observations with high probability; here p is a polynomial and the probability that the reconstruction succeeds converges to 1 as l-->[infinity].

Keywords: Scenery; reconstruction; Random; walk; Polynomially; many; observations (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304-4149(03)00085-1
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:107:y:2003:i:2:p:289-300

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().