Abstract: | Let ξ = (ξk)k∈? be i.i.d. with P(ξk = 0) = P(ξk = 1) = 1/2, and let S: = (Sk) be a symmetric random walk with holding on ?, independent of ξ. We consider the scenery ξ observed along the random walk path S, namely, the process (χk := ξ). With high probability, we reconstruct the color and the length of blockn, a block in ξ of length ≥ n close to the origin, given only the observations (χk). We find stopping times that stop the random walker with high probability at particular places of the scenery, namely on blockn and in the interval [?3n,3n]. Moreover, we reconstruct with high probability a piece of ξ of length of the order 3 around blockn, given only 3 observations collected by the random walker starting on the boundary of blockn. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 |