Reconstructing a piece of scenery with polynomially many observations. (Q2574598)

The scenery (a coloring of \(\mathbb Z\) with a finite set \(\mathcal {C} = \{1,2,\dots ,C\}\) of colors) reconstructing problem by a random walk is studied under the following assumptions: the scenery is i.i.d.\ uniformly colored, the random walk is recurrent, attaining every integer with a positive probability, and the number of possible single steps exceeds the number of colors. It is proved that for infinitely many \(n\) a finite piece of scenery of length \(\ell (n)=10\cdot 2^n+1\) around the origin can be reconstructed (up to a reflection and translation) with high probability from the first \(2n^7+2\cdot 2^{12\alpha n}\) observations with \(\alpha >0\). The optimal degree of the polynomial bound of the number of observations is not given but the authors conjecture that for any \(\varepsilon >0\), an algorithm can be found such that it reconstructs a piece of length \(\ell (n)\) around the origin with high probability from the first \(n^{2+\varepsilon }\) observations. Related results (partly from a not yet published paper by the same authors) are shortly reviewed, the reconstruction algorithm is defined and the theorem concerning its reconstructional ability is proved.