| Abstract | dc.description.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. | en |
