Finding blocks and other patterns in a random coloring of ℤ

Let ξ:= (ξ_k)_k∈ℤ be i.i.d. with P(ξ_k; = 1) = 1/2> and let S:= (S_k) _k∈ℕ0No 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:= ξs_k) k∈ℕ ₀. With high probability, we reconstruct the color and the length of blockⁿ, a block in ξof length ≥ n close to the origin, given only the observations (χk) k∈[0,2·3³ⁿ] We find stopping times that stop the random walker with high probability at particular places of the scenery, namely on blockⁿ and in the interval [-3 ⁿ, 3ⁿ]. Moreover, we reconstruct with high probability a piece of ξ of length of the order 3ⁿ0.2 around blockⁿ, given only 3[^n0.3] observations collected by the random walker starting on the boundary of blockⁿ.