Markers for error-corrupted observations

Abstract

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