Scenery reconstruction in two dimensions with many colors (Q1872360)

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.