Edge-reinforced random walk on a ladder. (English) Zbl 1102.82010

In the paper an edge-reinforced random walk on the ladder \(\mathbb Z\times \{1, 2\}\) is considered. The edges are undirected. They are assigned time-dependent random weights, with all initial edge weights equal to some constant \(a >0.\) In each step, the random walker jumps to a nearest-neighbor vertex with probability proportional to the weight of the traversed edge. Whenever the random walk crosses an edge, its weight is increased by 1.
The authors prove that the edge-reinforced random walk on \(\mathbb Z \times \{1, 2\}\) with initial weights \(a>3/4\) is recurrent. The problem is much more subtle than for acyclic graphs. They use the fact that the edge-reinforced random walk on a finite ladder has the same distribution as a random walk in an environment given by random time-independent edge weights. These edge weights are stochastically dependent in a complicated way.


82B41 Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60K37 Processes in random environments
Full Text: DOI arXiv


[1] Davis, B. (1990). Reinforced random walk. Probab. Theory Related Fields 84 203–229. · Zbl 0665.60077
[2] Diaconis, P. (1988). Recent progress on de Finetti’s notions of exchangeability. In Bayesian Statistics 3 111–125. Oxford Univ. Press, New York. · Zbl 0707.60033
[3] Diaconis, P. and Freedman, D. (1980). de Finetti’s theorem for Markov chains. Ann. Probab. 8 115–130. JSTOR: · Zbl 0426.60064
[4] Diaconis, P. and Rolles, S. W. W. (2004). Bayesian analysis for reversible Markov chains. · Zbl 1118.62085
[5] Doyle, P. G. and Snell, J. L. (2000). Random walks and electric networks. Available at http://arxiv.org/abs/math.PR/0001057. · Zbl 0583.60065
[6] Durrett, R., Kesten, H. and Limic, V. (2002). Once edge-reinforced random walk on a tree. Probab. Theory Related Fields 122 567–592. · Zbl 0995.60042
[7] Keane, M. S. and Rolles, S. W. W. (2000). Edge-reinforced random walk on finite graphs. In Infinite Dimensional Stochastic Analysis 217–234. Royal Netherland Academy of Arts and Sciences, Amsterdam. · Zbl 0986.05092
[8] Keane, M. S. and Rolles, S. W. W. (2002). Tubular recurrence. Acta Math. Hungar. 97 207–221. · Zbl 1026.60089
[9] Limic, V. (2003). Attracting edge property for a class of reinforced random walks. Ann. Probab. 31 1615–1654. · Zbl 1057.60048
[10] Pemantle, R. (1988). Phase transition in reinforced random walk and RWRE on trees. Ann. Probab. 16 1229–1241. JSTOR: · Zbl 0648.60077
[11] Pemantle, R. and Volkov, S. (1999). Vertex-reinforced random walk on \(\mathbbZ\) has finite range. Ann. Probab. 27 1368–1388. · Zbl 0960.60041
[12] Rolles, S. W. W. (2003). How edge-reinforced random walk arises naturally. Probab. Theory Related Fields 126 243–260. · Zbl 1029.60089
[13] Schaefer, H. (1974). Banach Lattices and Positive Operators . Springer, New York. · Zbl 0296.47023
[14] Sellke, T. (1993). Recurrence of reinforced random walk on a ladder. Technical Report 93-10, Purdue Univ. · Zbl 1113.60048
[15] Tarrès, P. (2004). Vertex-reinforced random walk on \(\mathbb Z\) eventually gets stuck on five points. Ann. Probab. 32 2650–2701. · Zbl 1068.60072
[16] Vervoort, M. (2000). Games, walks and grammars. Problems I’ve worked on. Ph.D. thesis, Univ. Amsterdam. · Zbl 1193.00001
[17] Volkov, S. (2001). Vertex-reinforced random walk on arbitrary graphs. Ann. Probab. 29 66–91. · Zbl 1031.60089
[18] Zaanen, A. C. (1997). Introduction to Operator Theory in Riesz Spaces . Springer, Berlin. · Zbl 0878.47022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.