×

Vertex-reinforced random walk. (English) Zbl 0741.60029

This paper considers a class of non-Markovian discrete-time random processes on a finite state space \(\{1,\dots,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. Let \(S_ i(n)\) keep track of the number of visits to state \(i\) up to time \(n\), and form the fractional occupation vector, \(V(n)\), where \(v_ i(n)=S_ i(n)/(\sum_{j=1}^ d S_ j(n))\). It is shown that \(V(n)\) converges to a set of critical points for the quadratic form \(H\) with matrix \(R\), and that under nondegeneracy conditions on \(R\), there is a finite set of points such that with probability one, \(V(n)\to p\) for some \(p\) in this set. There may be more than one \(p\) in this set for which \(P(V(n)\to p)>0\). On the other hand \(P(V(n)\to p)=0\) whenever \(p\) fails in a strong enough sense to be maximum for \(H\).

MSC:

60F99 Limit theorems in probability theory
60J99 Markov processes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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
[2] Davis, B.: Reinforced random walk. Probab. Theory Relat. Fields84, 203-229 (1990) · Zbl 0665.60077 · doi:10.1007/BF01197845
[3] Iosifescu, M., Theodorescu, R.: Random processes and learning. Berlin Heidelberg New York: Springer 1969 · Zbl 0194.51101
[4] Ortega, J.: Matrix theory: a second course. New York: Plenum Press 1987 · Zbl 0654.15001
[5] Pemantle, R.: Random processes with reinforcement. Doctoral thesis, Massachusetts Institute of Technology, 1988a · Zbl 0648.60077
[6] Pemantle, R.: Phase transition in reinforced random walk and RWRE on trees. Ann. Probab.16, 1229-1241 (1988b) · Zbl 0648.60077 · doi:10.1214/aop/1176991687
[7] Pemantle, R.: Nonconvergence to unstable points in urn models and stochastic approximations. Ann. Probab.18, 698-712 (1990) · Zbl 0709.60054 · doi:10.1214/aop/1176990853
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.