Finding blocks and other patterns in a random coloring of Z
2006; Wiley; Volume: 28; Issue: 1 Linguagem: Inglês
ISSN
1098-2418
AutoresHeinrich Matzinger, Silke W. W. Rolles,
Tópico(s)Markov Chains and Monte Carlo Methods
ResumoLet ξ = (ξk)k∈Z be i.i.d. with P(ξk = 0) = P(ξk = 1) = 1/2, and let S: = (Sk)k∈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 (χk := ξSk)k∈N0. 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)k∈[0,2·33n]. 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 3n0.2 around blockn, given only 3⌊n0.3⌋ observations collected by the random walker starting on the boundary of blockn. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006
Referência(s)