Vertex-reinforced random walk (Q1184048)

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\).