Markers for error-corrupted observations

Abstract

A scenery is a coloring #24; of the integers. Let (S(t))t#21;0 be a recurrent random walk on the integers. Observing the scenery #24; along the path of this random walk, one sees the color #24;(S(t)) at time t. The scenery reconstruction problem is concerned with trying to retrieve the scenery #24; , given only the sequence of observations #31; := (#24;(S(t)))t#21;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 #31;. 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.