Reconstructing a piece of scenery with polynomially many observations. (Q2574598): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q287730 |
Changed an Item |
||
Property / author | |||
Property / author: Silke W. W. Rolles / rank | |||
Normal rank |
Revision as of 14:45, 12 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reconstructing a piece of scenery with polynomially many observations. |
scientific article |
Statements
Reconstructing a piece of scenery with polynomially many observations. (English)
0 references
29 November 2005
0 references
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.
0 references
scenery reconstruction
0 references
random walk
0 references