Scenery reconstruction

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.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Bielefeld

Year

2009

Author dc:creator

• Pachón Pinzón, Angélica Yohana

Repository record source_url

https://pub.uni-bielefeld.de/record/2303375

OAI identifier oai:identifier

oai:pub.uni-bielefeld.de:2303375