Scenery reconstruction

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

Bielefelder E-Dissertation | Englisch
Pachón Pinzón, Angélica Yohana
Gutachter*in / Betreuer*in
Matzinger, Heinrich
Alternativer Titel
Abstract / Bemerkung
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.
Page URI


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, Angélica Yohana. 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.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
Dieses Objekt ist durch das Urheberrecht und/oder verwandte Schutzrechte geschützt. [...]
Access Level
OA Open Access
Zuletzt Hochgeladen
MD5 Prüfsumme


Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Suchen in

Google Scholar