Vertex-reinforced random walk on \(\mathbb Z\) has finite range. (English) Zbl 0960.60041

Pemantle, Robin; Volkov, Stanislav

Ann. Probab. 27, No. 3, 1368-1388 (1999).

The stochastic process called vertex-reinforced random walk has been defined by the first named author [Ann. Probab. 16, No. 3, 1229-1241 (1988; Zbl 0648.60077)]. In the present paper this process is considered in the case where the underlying graph is \(\mathbb Z\). The authors show that the range is almost surely finite, that at least five points are visited infinitely often almost surely, and that with positive probability the range contains exactly five points. There are always points visited infinitely often but at a set of times of zero density, and the number of visits to such a point by time \(n\) may be asymptotically \(n^\alpha\) for a dense set of values \(\alpha\in(0,1)\). The power law analysis relies on analysis of a related urn model generalizing both Pólya’s and Friedman’s urn.

Reviewer: Marius Iosifescu (Bucureşti)

MSC:

60G17	Sample path properties
60J20	Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)

Citations:

Zbl 0648.60077

References:

[1]	ARTHUR, B. 1986. Industry location patterns and the importance of history. Center for Economic Policy Research Paper 84. Stanford Univ.
[2]	ARTHUR, B., ERMOLIEV, Y. and KANIOVSKI, Y. 1987. Path-dependent processes and the emergence of macro-structure. European J. Oper. Res. 30 294 303.
[3]	ATHREYA, K. 1967. Doctoral dissertation, Stanford Univ.
[4]	ATHREYA, K. and NEY, P. 1972. Branching Processes. Springer, New York. · Zbl 0259.60002
[5]	BLACKWELL, D. and MCQUEEN, J. 1973. Ferguson distributions via Polya urn schemes. Ann. Ḿath. Statist. 1 353 355. · Zbl 0276.62010 · doi:10.1214/aos/1176342372
[6]	COOPERSMITH, D. and DIACONIS, P. 1987. Random walks with reinforcement. Unpublished manuscript.
[7]	DAVIS, B. 1990. Reinforced random walk. Probab. Theory Related Fields 84 203 229. \" · Zbl 0665.60077 · doi:10.1007/BF01197845
[8]	EGGENBERGER, F. and POLYA, G. 1923. Uber die Statistik verketter Vorgange. Zeit. Angew. \' \" Math. Mech. 3 279 289.
[9]	FELLER, W. 1971. Introduction to Probability Theory and Its Applications, 2nd ed. Wiley, New York. · Zbl 0219.60003
[10]	FREEDMAN, D. 1965. Bernard Friedman’s urn. Ann. Math. Statist. 36 956 970. · Zbl 0138.12003 · doi:10.1214/aoms/1177700068
[11]	FRIEDMAN, B. 1949. A simple urn model. Comm. Pure Appl. Math. 2 59 70. · Zbl 0033.07101 · doi:10.1002/cpa.3160020103
[12]	GREENWOOD, M. and YULE, G. U. 1920. Inquiry into the nature of frequency distributions representative of multiple happenings with particular reference to the occurrence of multiple attacks of disease or of repeated accidents. J. Roy. Statist. Soc. 83 255 279.
[13]	IOSIFESCU, M. and THEODORESCU, R. 1969. Random Processes and Learning. Springer, New York. · Zbl 0194.51101
[14]	KUSHNER, H. and YIN, G. 1997. Stochastic Approximation Algorithms and Applications. Springer, New York. · Zbl 0914.60006
[15]	MAULDIN, D., SUDDERTH, B. and WILLIAMS, S. 1992. Polya trees and random distributions. Ann. Ḿath. Statist. 20 1203 1221. · Zbl 0765.62006
[16]	OTHMER, H. and STEVENS, A. 1998. Aggregation, blowup, and collapse: the ABC’s of taxis in reinforced random walk. SIAM J. Appl. Math. 57 1044 1081. JSTOR: · Zbl 0990.35128 · doi:10.1137/S0036139995288976
[17]	PEMANTLE, R. 1988a. Random processes with reinforcement. Ph.D. dissertation, MIT.
[18]	PEMANTLE, R. 1988b. Phase transition in reinforced random walk and RWRE on trees. Ann. Probab. 16 1229 1241. · Zbl 0648.60077 · doi:10.1214/aop/1176991687
[19]	PEMANTLE, R. 1992. Vertex reinforced random walk. Probab. Theory Related Fields 92 117 136. · Zbl 0741.60029 · doi:10.1007/BF01205239
[20]	ROBBINS, H. and MONRO, S. 1951. A stochastic approximation method. Ann. Math. Statist. 22 400 407. · Zbl 0054.05901 · doi:10.1214/aoms/1177729586
[21]	SELLKE, T. 1994. Reinforced random walk on the d-dimensional integer lattice. · Zbl 1154.82011
[22]	MADISON, WISCONSIN 53706 CANADA M5T 3J1