Summary
This paper considers a class of non-Markovian discrete-time random processes on a finite state space {1,...,d}. The transition probabilities at each time are influenced by the number of times each state has been visited and by a fixed a priori likelihood matrix,R, which is real, symmetric and nonnegative. LetS i (n) keep track of the number of visits to statei up to timen, and form the fractional occupation vector,V(n), where\(v_i (n) = {{S_i (n)} \mathord{\left/ {\vphantom {{S_i (n)} {\left( {\sum\limits_{j = 1}^d {S_j (n)} } \right)}}} \right. \kern-\nulldelimiterspace} {\left( {\sum\limits_{j = 1}^d {S_j (n)} } \right)}}\). It is shown thatV(n) converges to to a set of critical points for the quadratic formH with matrixR, and that under nondegeneracy conditions onR, there is a finite set of points such that with probability one,V(n)→p for somep in the set. There may be more than onep in this set for whichP(V(n)→p)>0. On the other handP(V(n)→p)=0 wheneverp fails in a strong enough sense to be maximum forH.
Article PDF
Similar content being viewed by others
References
Diaconis, P.: Recent progress on de Finetti's notions of exchangeability. Bayesian statistics, vol. 3, pp 111–125. Valencia 1987. Oxford Sci. Publ. New York: Oxford University Press 1988
Davis, B.: Reinforced random walk. Probab. Theory Relat. Fields84, 203–229 (1990)
Iosifescu, M., Theodorescu, R.: Random processes and learning. Berlin Heidelberg New York: Springer 1969
Ortega, J.: Matrix theory: a second course. New York: Plenum Press 1987
Pemantle, R.: Random processes with reinforcement. Doctoral thesis, Massachusetts Institute of Technology, 1988a
Pemantle, R.: Phase transition in reinforced random walk and RWRE on trees. Ann. Probab.16, 1229–1241 (1988b)
Pemantle, R.: Nonconvergence to unstable points in urn models and stochastic approximations. Ann. Probab.18, 698–712 (1990)
Author information
Authors and Affiliations
Additional information
This research was supported by an NSF graduate fellowship and by an NSF postdoctoral fellowship
Rights and permissions
About this article
Cite this article
Pemantle, R. Vertex-reinforced random walk. Probab. Th. Rel. Fields 92, 117–136 (1992). https://doi.org/10.1007/BF01205239
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01205239