Reconstructing a random scenery in polynomial time
Heinrich Matzinger, Sww Silke Rolles · TU/e Research Portal · 2002
Benjamini asked whether the scenery reconstruction problem can be solved in polynomial time.In this article, we answer his question in the armative for an i.i.d.uniformly colored scenery on Z observed along a random walk path with bounded jumps.We assume the random walk is recurrent, can reach every integer with positive probability, and the number of possible single steps for the random walk exceeds the number of colors.We prove that a nite piece of scenery of length l around the origin can be reconstructed up to reection and a small translation from the rst p(l) observations with high probability here p is a polynomial and the probability that the reconstruction succeeds converges to 1 as l ! 1 .