Finding blocks and other patterns in a random coloring of Z
Let xi := (xi(k))(k is an element of Z) be i.i.d. with P(xi(k) = 0) = P(xi(k) = 1) = 1/2, and let S := (S(k))(k is an element of N0) be a symmetric random walk with holding on Z, independent of. We consider the scenery observed along the random walk path S, namely, the process (X(k) := xi s(k))(k is an element of N0) With high probability, we reconstruct the color and the length of block", a block in of length >= it close to the origin, given only the observations (X(k))(k is an element of[0,2.33n]). 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(n), 3(n)]. Moreover, we reconstruct with high probability a piece of of length of the order 3,0,2 around block", given only 3[n(0.3)] observations collected by the random walker starting on the boundary of block". (c) 2005 Wiley Periodicals, Inc.
random walk random media scenery reconstruction polynomial algorithm