Scenery reconstruction

Pachón Pinzón AY (2009)
Bielefeld (Germany): Bielefeld University.

Bielefeld Dissertation | English
Matzinger, Heinrich (HD Dr. habil.)
Alternative Title
Suppose that to each site on the integer numbers a color from the set 0, 1,..., C -1 is assigned. This defines a coloration of Z which is called scenery. Suppose a simple random walk starts to move registering the color it sees at each time t > 0 and producing a new sequence of colors, i.e, at time t, the random walk sees the color where it is on. Scenery Reconstruction problem can be described by the next question: Can the original coloring be reconstructed given only one realization of the observations? This thesis presents three new results about Scenery Reconstruction. The first of them shows how to reconstruct a finite piece of scenery close to the origin. For the reconstruction we only use polynomially many observations (in the length of the piece). The scenery is taken to have 3 colors. The algorithm uses a method which is also used for DNA-reconstruction: it first obtains micro-strings which it then assembles. The micro-strings are of logarithmic order in the length of the piece to be reconstructed. The second result presents a fundamental improvement for determining times when the walker is close to the origin. A simple approach to solving this problem is presented by Hart, Machado and Matzinger 2009, but that approach fails with less than five colors. Here is boosted the proof to make it works with only 4 colors. The approach should also be useful in the future for the reconstruction of sceneries with low entropy. Finally, the third result shows how to implement practically the algorithm obtained by the first one and present computer simulations.

Cite this

Pachón Pinzón AY. Scenery reconstruction. Bielefeld (Germany): Bielefeld University; 2009.
Pachón Pinzón, A. Y. (2009). Scenery reconstruction. Bielefeld (Germany): Bielefeld University.
Pachón Pinzón, A. Y. (2009). Scenery reconstruction. Bielefeld (Germany): Bielefeld University.
Pachón Pinzón, A.Y., 2009. Scenery reconstruction, Bielefeld (Germany): Bielefeld University.
A.Y. Pachón Pinzón, Scenery reconstruction, Bielefeld (Germany): Bielefeld University, 2009.
Pachón Pinzón, A.Y.: Scenery reconstruction. Bielefeld University, Bielefeld (Germany) (2009).
Pachón Pinzón, Angélica Yohana. Scenery reconstruction. Bielefeld (Germany): Bielefeld University, 2009.
Main File(s)
File Name
Access Level
OA Open Access

This data publication is cited in the following publications:
This publication cites the following data publications:


0 Marked Publications

Open Data PUB

Search this title in

Google Scholar