Reconstructing a piece of scenery with polynomially many observations. (Q2574598): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0304-4149(03)00085-1 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2110598314 / rank | |||
Normal rank |
Latest revision as of 10:12, 30 July 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
0 references