Finding blocks and other patterns in a random coloring of ℤ

Heinrich Matzinger, Silke W.W. Rolles

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

Let ξ:= (ξk)k∈ℤ be i.i.d. with P(ξk; = 1) = 1/2> and let S:= (Sk) 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:= ξsk) k∈ℕ 0. 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 [-3 n, 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.

Original languageEnglish
Pages (from-to)37-75
Number of pages39
JournalRandom Structures and Algorithms
Volume28
Issue number1
DOIs
StatePublished - Jan 2006
Externally publishedYes

Keywords

  • Polynomial algorithm
  • Random media
  • Random walk
  • Scenery reconstruction

Fingerprint

Dive into the research topics of 'Finding blocks and other patterns in a random coloring of ℤ'. Together they form a unique fingerprint.

Cite this