Detecting the trail of a random walker in a random scenery
Yuval Peres (Microsoft Research)
Abstract
Suppose that the vertices of the lattice $\mathbb{Z}^d$ are endowed with a random scenery, obtained by tossing a fair coin at each vertex. A random walker, starting from the origin, replaces the coins along its path by i.i.d. biased coins. For which walks and dimensions can the resulting scenery be distinguished from the original scenery? We find the answer for simple random walk, where it does not depend on dimension, and for walks with a nonzero mean, where a transition occurs between dimensions three and four. We also answer this question for other types of graphs and walks, and raise several new questions.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 1-18
Publication Date: October 3, 2013
DOI: 10.1214/EJP.v18-2367
References
- Arias-Castro, Ery; Candès, Emmanuel J.; Helgason, Hannes; Zeitouni, Ofer. Searching for a trail of evidence in a maze. Ann. Statist. 36 (2008), no. 4, 1726--1757. MR2435454
- Benjamini, Itai; Pemantle, Robin; Peres, Yuval. Unpredictable paths and percolation. Ann. Probab. 26 (1998), no. 3, 1198--1211. MR1634419
- Benjamini, Itai; Peres, Yuval. Tree-indexed random walks on groups and first passage percolation. Probab. Theory Related Fields 98 (1994), no. 1, 91--112. MR1254826
- Berger, Noam. Transience, recurrence and critical behavior for long-range percolation. Comm. Math. Phys. 226 (2002), no. 3, 531--558. MR1896880
- Bolthausen, Erwin; Sznitman, Alain-Sol. On the static and dynamic points of view for certain random walks in random environment. Special issue dedicated to Daniel W. Stroock and Srinivasa S. R. Varadhan on the occasion of their 60th birthday. Methods Appl. Anal. 9 (2002), no. 3, 345--375. MR2023130
- Cox, J. Theodore; Durrett, Richard. Oriented percolation in dimensions $d\geq 4$: bounds and asymptotic formulas. Math. Proc. Cambridge Philos. Soc. 93 (1983), no. 1, 151--162. MR0684285
- Durrett, Richard. Probability: theory and examples. Second edition. Duxbury Press, Belmont, CA, 1996. xiii+503 pp. ISBN: 0-534-24318-5 MR1609153
- Häggström, Olle; Mossel, Elchanan. Nearest-neighbor walks with low predictability profile and percolation in $2+\epsilon$ dimensions. Ann. Probab. 26 (1998), no. 3, 1212--1231. MR1640343
- Lawler, Gregory F. Intersections of random walks. Probability and its Applications. Birkhäuser Boston, Inc., Boston, MA, 1991. 219 pp. ISBN: 0-8176-3557-2 MR1117680
- Levin, David A.; Pemantle, Robin; Peres, Yuval. A phase transition in random coin tossing. Ann. Probab. 29 (2001), no. 4, 1637--1669. MR1880236
- Lyons, Russell. Random walks and percolation on trees. Ann. Probab. 18 (1990), no. 3, 931--958. MR1062053
- Russell Lyons with Yuval Peres. Probability on trees and networks. 2012. Cambridge University Press, in preparation. Available at http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html.
This work is licensed under a Creative Commons Attribution 3.0 License.