TY  - THES
AB  - 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.
DA  - 2009
LA  - eng
PY  - 2009
TI  - Scenery reconstruction
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:361-15511
Y2  - 2024-11-22T05:02:53
ER  -