Finding blocks and other patterns in a random coloring of ℤ

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