Premium
Finding blocks and other patterns in a random coloring of ℤ
Author(s) -
Matzinger Heinrich,
Rolles Silke W.W.
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20110
Subject(s) - random walk , block (permutation group theory) , combinatorics , interval (graph theory) , mathematics , path (computing) , struct , boundary (topology) , discrete mathematics , computer science , statistics , mathematical analysis , programming language
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