×

zbMATH — the first resource for mathematics

Attracting edge property for a class of reinforced random walks. (English) Zbl 1057.60048
The author considers the so-called edge-reinforced random walk with weight function \(W\) on a connected (unoriented) graph of bounded degree. That is, the walker jumps along the edges, and the probability along a given edge is given by the quotient of the value of \(W\) of the number of previous jumps along that edge, divided by the sum of all the \(W\)-values of the number of previous jumps along all the adjacent edges of the present site. Here \(W\) is a positive weight function, which is assumed to be \(W(k)=k^\rho\) for some \(\rho>1\).
It was previously known that, for the graph \(\mathbb Z^ d\), under the condition \(\sum_{k\in\mathbb N}1/W(k)<\infty\), there is almost surely one (random) attracting edge which is traversed infinitely often. The present paper strengthens this result for arbitrary bounded-degree graphs with \(W(k)=k^\rho\) for some \(\rho>1\), by showing that this edge is unique, almost surely. The main tools are martingale techniques and a comparison to the generalized urn scheme. The assumption that \(W(k)=k^\rho\) is crucial for most of the arguments.

MSC:
60G50 Sums of independent random variables; random walks
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] ATHREy A, K. B. and KARLIN, S. (1986). Embedding of Urn schemes into continuous time Markov branching processes and related limit theorems. Ann. Math. Statist. 39 1801- 1817. · Zbl 0185.46103 · doi:10.1214/aoms/1177698013
[2] DAVIS, B. (1990). Reinforced random walk. Probab. Theory Random Fields 84 203-229. · Zbl 0665.60077 · doi:10.1007/BF01197845
[3] DIACONIS, P. (1988). Recent progress on de Finetti’s notion of exchangeability. In Bayesian Statistics 3 (J. M. Bernardo, M. H. DeGroot, D. V. Lindley and A. F. M. Smith, eds.) 43-110. Oxford Univ. Press. · Zbl 0707.60033
[4] DURRETT, R. (1991). Probability: Theory and Examples. Wadsworth and Brooks/Cole, Belmont, CA. · Zbl 0709.60002
[5] 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 · doi:10.1007/s004400100179
[6] HILL, B. M., LANE, D. and SUDDERTH, W. A. (1980). Strong law for some generalized urn processes. Ann. Probab. 8 214-226. · Zbl 0429.60021 · doi:10.1214/aop/1176994772
[7] KEANE, M. S. and ROLLES, S. W. W. (2000). Edge-reinforced random walk on finite graphs. In Infinite Dimensional Stochastic Analy sis (P. Clement, F. den Hollander, J. van Neerven and B. de Pagter, eds.) 217-234. Roy al Netherlands Academy of Arts and Sciences, Amsterdam. · Zbl 0986.05092
[8] PEMANTLE, R. (1988). Phase transition in reinforced random walk and RWRE on trees. Ann. Probab. 16 1229-1241. · Zbl 0648.60077 · doi:10.1214/aop/1176991687
[9] PEMANTLE, R. (1992). Vertex-reinforced random walk. Probab. Theory Related Fields 92 117-136. · Zbl 0741.60029 · doi:10.1007/BF01205239
[10] PEMANTLE, R. (2001). Random processes with reinforcement.
[11] PEMANTLE, R. and VOLKOV, S. (1999). Vertex-reinforced random walk on Z has finite range. Ann. Probab. 27 1368-1388. · Zbl 0960.60041 · doi:10.1214/aop/1022677452
[12] SELLKE, T. (1994). Reinforced random walks on the d-dimensional integer lattice. · Zbl 1154.82011
[13] TARRÈS, P. (2001). VRRW on Z eventually gets stuck at a set of five points.
[14] TÓTH, B. (1997). Limit theorems for weakly reinforced random walks on Z. Studia Sci. Math. Hungar. 33 321-337. · Zbl 0912.60043
[15] VOLKOV, S. (2001). Vertex-reinforced random walk on arbitrary graphs. Ann. Probab. 29 66-91. · Zbl 1031.60089 · doi:10.1214/aop/1008956322
[16] VANCOUVER, BRITISH COLUMBIA CANADA V6T 1Z2 E-MAIL: limic@math.ubc.ca
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.