Bounding a Random Environment Bounding a Random Environment for Two-dimensional Edge-reinforced Random Walk

Franz Merkl (University of Munich, Germany)
Silke W.W. Rolles (Technical University of Munich)


We consider edge-reinforced random walk on the infinite two-dimensional lattice. The process has the same distribution as a random walk in a certain strongly dependent random environment, which can be described by random weights on the edges. In this paper, we show some decay properties of these random weights. Using these estimates, we derive bounds for some hitting probabilities of the edge-reinforced random walk.

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

Pages: 530-565

Publication Date: April 12, 2008

DOI: 10.1214/EJP.v13-495


  1. Coppersmith, D.; Diaconis, P. Random walk with reinforcement. Unpublished manuscript (1986).
  2. Diaconis, P.; Freedman, D. de Finetti's theorem for Markov chains. Ann. Probab. 8 (1980), no. 1, 115--130. Math. Review 0556418 (81f:60090)
  3. Diaconis, P. Recent progress on de Finetti's notions of exchangeability. Bayesian statistics, 3 (Valencia, 1987), 111--125, Oxford Sci. Publ., Oxford Univ. Press, New York, 1988. Math. Review 1008047 (90h:60035)
  4. Diaconis, P.; Rolles, S. Bayesian analysis for reversible Markov chains. Ann. Statist. 34 (2006), no. 3, 1270--1292. Math. Review 2278358
  5. Keane, M. S.; Rolles, S. Edge-reinforced random walk on finite graphs. Infinite dimensional stochastic analysis (Amsterdam, 1999), 217--234, Verh. Afd. Natuurkd. 1. Reeks. K. Ned. Akad. Wet., 52, R. Neth. Acad. Arts Sci., Amsterdam, 2000. Math. Review 1832379 (2002b:60078)
  6. Maurer, S. B. Matrix generalizations of some theorems on trees, cycles and cocycles in graphs. SIAM J. Appl. Math. 30 (1976), no. 1, 143--148. Math. Review 0392635 (52 #13452)
  7. Merkl, F.; Rolles, S. Edge-reinforced random walk on a ladder. Ann. Probab. 33 (2005), no. 6, 2051--2093. Math. Review 2184091 (2006h:60152)
  8. Merkl, F.; Rolles, S. Edge-reinforced random walk on one-dimensional periodic graphs. Accepted for publication in Probab. Theory Related Fields. Preprint available from, (2006).
  9. Merkl, F.; Rolles, S. Linearly edge-reinforced random walks. Dynamics & stochastics, 66--77, IMS Lecture Notes Monogr. Ser., 48, Inst. Math. Statist., Beachwood, OH, 2006. Math. Review 2306189 (2008c:82035)
  10. Merkl, F.; Rolles, S. Asymptotic behavior of edge-reinforced random walks. Ann. Probab. 35 (2007), no. 1, 115--140. Math. Review 2303945 (2008b:60217)
  11. Merkl, F.; Rolles, S. Recurrence of edge-reinforced random walk on a two-dimensional graph. Preprint available from, (2007).
  12. Merkl, F.; Rolles, S. A random environment for linearly edge-reinforced random walks on infinite graphs. Probab. Theory Related Fields 138 (2007), no. 1-2, 157--176. Math. Review 2288067
  13. Pemantle, R.. Phase transition in reinforced random walk and RWRE on trees. Ann. Probab. 16 (1988), no. 3, 1229--1241. Math. Review 0942765 (89g:60220)
  14. Rolles, S. How edge-reinforced random walk arises naturally. Probab. Theory Related Fields 126 (2003), no. 2, 243--260. Math. Review 1990056 (2004c:60276)
  15. Rolles, S. On the recurrence of edge-reinforced random walk on Z x G. Probab. Theory Related Fields 135 (2006), no. 2, 216--264. Math. Review 2218872 (2007b:60246)
  16. Sellke, T. Reinforced random walk on the d-dimensional integer lattice. Technical report 94-26, Purdue University, (1994)

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