Reconstructing a Multicolor Random Scenery seen along a Random Walk Path with Bounded Jumps

Matthias Loewe (University Muenster)
Heinrich Matzinger (Georgia Tech)
Franz Merkl (Leiden University)

Abstract


Kesten noticed that the scenery reconstruction method proposed by Matzinger in his PhD thesis relies heavily on the skip-free property of the random walk. He asked if one can still reconstruct an i.i.d. scenery seen along the path of a non-skip-free random walk. In this article, we positively answer this question. We prove that if there are enough colors and if the random walk is recurrent with at most bounded jumps, and if it can reach every integer, then one can almost surely reconstruct almost every scenery up to translations and reflections. Our reconstruction method works if there are more colors in the scenery than possible single steps for the random walk.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 436-507

Publication Date: June 8, 2004

DOI: 10.1214/EJP.v9-206

References

  1. Benjamini, Itai; Kesten, Harry. Distinguishing sceneries by observing the scenery along a random walk path. J. Anal. Math. 69 (1996), 97--135. Math. Review 1428097
  2. Burdzy, Krzysztof. Some path properties of iterated Brownian motion. Seminar on Stochastic Processes, 1992 (Seattle, WA, 1992), 67--87, Progr. Probab., 33, Birkhäuser Boston, Boston, MA, 1993. Math. Review 1278077
  3. den Hollander, Frank; Steif, Jeffrey E. Mixing properties of the generalized $T,Tsp {-1}$-process. J. Anal. Math. 72 (1997), 165--202. Math. Review 1482994
  4. den Hollander, W. Th. F. Mixing properties for random walk in random scenery. Ann. Probab. 16 (1988), no. 4, 1788--1802. Math. Review 0958216
  5. Durrett, Richard. Probability: theory and examples. Second edition. Duxbury Press, Belmont, CA, 1996. xiii+503 pp. ISBN: 0-534-24318-5 Math. Review 1609153
  6. Howard, C. Douglas. Detecting defects in periodic scenery by random walks on $ Z$. Random Structures Algorithms 8 (1996), no. 1, 59--74. Math. Review 1368850
  7. Howard, C. Douglas. Orthogonality of measures induced by random walks with scenery. Combin. Probab. Comput. 5 (1996), no. 3, 247--256. Math. Review 1411085
  8. Howard, C. Douglas. Distinguishing certain random sceneries on $ Z$ via random walks. Statist. Probab. Lett. 34 (1997), no. 2, 123--132. Math. Review 1457504
  9. Kalikow, Steven Arthur. $T,,Tsp{-1}$ transformation is not loosely Bernoulli. Ann. of Math. (2) 115 (1982), no. 2, 393--409.Math. Review 0647812
  10. Keane, M.; den Hollander, W. Th. F. Ergodic properties of color records. Phys. A 138 (1986), no. 1-2, 183--193.Math. Review 0865242
  11. Kesten, Harry.Detecting a single defect in a scenery by observing the scenery along a random walk path. Itô's stochastic calculus and probability theory, 171--183, Springer, Tokyo, 1996.Math. Review 1439524 Kesten, Harry.Distinguishing and reconstructing sceneries from observations along random walk paths. Microsurveys in discrete probability (Princeton, NJ, 1997), 75--83, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 41, Amer. Math. Soc., Providence, RI, 1998.Math. Review 1630410
  12. Lenstra, Andries; Matzinger, Heinrich. Reconstructing a 4-color scenery by observing it along a recurrent random walk path with unbounded jumps. In preparation (2004).Math. Review number not available.
  13. Lindenstrauss, Elon.Indistinguishable sceneries. Random Structures Algorithms 14 (1999), no. 1, 71--86.Math. Review 1662199
  14. Löwe, Matthias; Matzinger, Heinrich, III. Scenery reconstruction in two dimensions with many colors.Ann. Appl. Probab. 12 (2002), no. 4, 1322--1347.Math. Review 1936595
  15. Löwe, Matthias; Matzinger, Heinrich, III. Reconstruction of sceneries with correlated colors. Stochastic Process. Appl. 105 (2003), no. 2, 175--210.Math. Review 1978654
  16. Löwe, Matthias; Matzinger, Heinrich, III. Reconstructing a three-color scenery by observing it along a simple random walk path. Random Structures Algorithms 15 (1999), no. 2, 196--207.Math. Review 1704344
  17. Matzinger, Heinrich; Rolles, Silke W. W. Finding blocks and other patterns in a random coloring of Z. Preprint no. 03-044 in http://www.mathematik.uni-bielefeld.de/fgweb/Preprints/index03.html (2003). Math. Review number not available.
  18. Matzinger, Heinrich; Rolles, Silke W. W. Reconstructing a piece of scenery with polynomially many observations. Stochastic Process. Appl. 107 (2003), no. 2, 289--300. Math. Review 1999792
  19. Matzinger, Heinrich; Rolles, Silke W. W. Reconstructing a random scenery observed with random errors along a random walk path. Probab. Theory Related Fields 125 (2003), no. 4, 539--577.Math. Review 1974414
  20. Matzinger, Heinrich; Rolles, Silke W. W.Retrieving random media. Preprint no. 03-043 in http://www.mathematik.uni-bielefeld.de/fgweb/Preprints/index03.html (2003). Math. Review number not available.
  21. Spitzer, Frank. Principles of random walks.Second edition. Graduate Texts in Mathematics, Vol. 34. Springer-Verlag, New York-Heidelberg, 1976. xiii+408 pp.Math. Review 0388547
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.