Markers for error-corrupted observations

Andrew Hart and Heinrich Matzinger

Stochastic Processes and their Applications, 2006, vol. 116, issue 5, 807-829

Abstract: A scenery is a coloring [xi] of the integers. Let (S(t))t>=0 be a recurrent random walk on the integers. Observing the scenery [xi] along the path of this random walk, one sees the color [xi](S(t)) at time t. The scenery reconstruction problem is concerned with trying to retrieve the scenery [xi], given only the sequence of observations [chi]:=([xi](S(t)))t>=0. Russel Lyons and Yuval Peres have both posed the question of whether two-color sceneries can be reconstructed when the observations are corrupted by random errors. The random errors happening at different times are independent conditional on [chi]. It has been proved that it is possible to do reconstruction in the case where the observations are contaminated with errors and the scenery has several colors, provided the error probability is small enough. However, the reconstruction problem is more difficult with fewer colors. Although the scenery reconstruction problem for two-color sceneries from error-free observations has been solved, the reconstruction of two-color sceneries from error-corrupted observations remains an open problem. In this paper, we solve one of the two remaining problems needed in order to reconstruct two-color sceneries when the observations are corrupted with random errors. We prove that given only the corrupted observations, we are able to determine a large amount of times, when the random walk is back at the same place (marker) in the scenery.

Keywords: Scenery; reconstruction; Scenery; distinguishing; Large; deviations (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304-4149(05)00169-9
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:116:y:2006:i:5:p:807-829

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 ().