Reconstructing a piece of 2-color scenery
Jüri Lember, Heinrich Matzinger · TU/e Research Portal · 2003
We consider a sequence of observations obtained along a random walk from an infinite binary code (scenery). The scenery reconstruction problem is concerned with trying to retrieve the scenery, given only the observations. In an earlier paper by Matzinger et al., the problem was solved for a scenery with sufficiently many colors. This proof does not apply in two color case, and the question of reconstructing the two-color scenery, observed along a random walk with bounded jumps, has not been answered. In this paper we show that, given some preliminary information, a long piece of two-color scenery can be reconstructed with high probability. This is the main ingredient (so-called zag-step) for the whole algorithm for two-color scenery reconstruction.