Vertex-reinforced random walk
type: Item
instance of: scholarly article
title: Vertex-reinforced random walk
zbMATH Open document ID: 0741.60029
DOI: 10.1007/BF01205239
author: Robin Pemantle
publication date: 1992-06-28T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 60F99
Mathematics Subject Classification ID: 60J99
zbMATH DE Number: 34023
zbMATH Keywords: discrete-time random processes
zbMATH Keywords: a priori likelihood matrix
zbMATH Keywords: fractional occupation vector
MaRDI profile type: Publication
cites work: Reinforced random walk
cites work: Q5590550
cites work: Q3800193
cites work: Phase transition in reinforced random walk and RWRE on trees
cites work: Nonconvergence to unstable points in urn models and stochastic approximations
published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
Recommended article: Vertex-reinforced random walk on arbitrary graphs
Recommended article: Dynamics of vertex-reinforced random walks
Recommended article: A note on vertex-reinforced random walks.
Recommended article: Vertex-reinforced random walks and a conjecture of Pemantle
Recommended article: Vertex reinforced random walks with exponential interaction on complete graphs
description: scientific article; zbMATH DE number 34023