TY - JOUR

T1 - Reconstructing a piece of scenery with polynomially many observations

AU - Matzinger, H.

AU - Rolles, S.W.W.

PY - 2003

Y1 - 2003

N2 - Benjamini asked whether the scenery reconstruction problem can be solved using only polynomially many observations. In this article, we answer his question in the affirmative for an i.i.d. uniformly colored scenery on 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. For infinitely many l, we prove that a finite piece of scenery of length l around the origin can be reconstructed up to reflection and a small translation from the first p(l) observations with high probability; here p is a polynomial and the probability that the reconstruction succeeds converges to 1 as l¿8.

AB - Benjamini asked whether the scenery reconstruction problem can be solved using only polynomially many observations. In this article, we answer his question in the affirmative for an i.i.d. uniformly colored scenery on 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. For infinitely many l, we prove that a finite piece of scenery of length l around the origin can be reconstructed up to reflection and a small translation from the first p(l) observations with high probability; here p is a polynomial and the probability that the reconstruction succeeds converges to 1 as l¿8.

U2 - 10.1016/S0304-4149(03)00085-1

DO - 10.1016/S0304-4149(03)00085-1

M3 - Article

VL - 107

SP - 289

EP - 300

JO - Stochastic Processes and their Applications

JF - Stochastic Processes and their Applications

SN - 0304-4149

IS - 2

ER -