Scenery reconstruction in two dimensions with many colors
type: Item
instance of: scholarly article
title: Scenery reconstruction in two dimensions with many colors
zbMATH Open document ID: 1018.60100
author: Heinrich Matzinger
author: M. Löwe
published in: The Annals of Applied Probability
publication date: 2003-05-06T00:00:00Z
review text: The two-dimensional scenery is a function \(\xi :Z^2\to Z.\) For \(D\subset Z^2, \;\;\xi :D\to Z\) is called a piece of scenery. If the range of \(\xi\) contains exactly \(m\) elements, then say that \(\xi\) has \(m\) colors. \(\xi\) and \(\overline{\xi}\) are equivalent if they can be obtained from each other by translation and reflection on the coordinate axes. In the paper \(\xi\) is the result from an unbiased i.i.d. random process with \(m\) colors; that is \(\xi(v)\) are i.i.d. for all \(v\in Z^2\) and \(P(\xi(0)=i)=1/m\) for all colors \(i\in \{0,1,...,m-1\}.\) Let \((S_k)_{k\in N}\) be a simple, symmetric random walk in two dimensions starting at the origin. The main result of the paper states that if \(m\) is large enough, the color record of \((S_k)\), that is \(\chi:=(\xi(S_k))_{k\in N},\) contains enough information to reconstruct \(\xi\) almost surely up to equivalence. Also a well-defined algorithm that gives the scenery with probability larger than \(1/2\) is presented.
Mathematics Subject Classification ID: 60K37
zbMATH DE Number: 1906150
zbMATH Keywords: scenery
zbMATH Keywords: random walk
zbMATH Keywords: coloring
reviewed by: U. A. Rozikov
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1037125865
OpenAlex ID: W2150828054
cites work: Distinguishing sceneries by observing the scenery along a random walk path
cites work: Ergodic properties of color records
cites work: The transient behaviour of the simple random walk in the plane
cites work: Q5807214
cites work: Some problems concerning the structure of random walk paths
cites work: Detecting defects in periodic scenery by random walks on Z
cites work: Q4208450
cites work: Indistinguishable Sceneries
cites work: Q4265789
cites work: Estimates of the largest disc covered by a random walk
cites work: Q5731217
cites work: A new look at independence
DOI: 10.1214/AOAP/1037125865
description: scientific article; zbMATH DE number 1906150