Vertex-reinforced random walk on arbitrary graphs (Q1872176): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: math/9907196 / rank | |||
Normal rank |
Revision as of 22:29, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Vertex-reinforced random walk on arbitrary graphs |
scientific article |
Statements
Vertex-reinforced random walk on arbitrary graphs (English)
0 references
6 May 2003
0 references
Vertex-reinforced random walk (VRRW) on a graph \(G\) is a process which moves, at time \(n\), from a vertex to its neighbours with probabilities proportional to the local times of these neighbour vertices at time \(n\) (where the initial local time is set to \(1\), for all vertices of the graph). In other words, VRRW is a random process in a continuously changing random environment which is more likely to visit vertices it has visited before. The author shows that under very mild conditions on the graph, the probability that VRRW visits only finitely many vertices is strictly positive. In particular, this is the case if the graph has bounded degree or if the graph does not contain triangles. He also shows that on a tree of bounded degree, VRRW visits only finitely many vertices with probability \(1\), and conjectures that this holds true for any graph of bounded degree. Further, the paper contains several results on the patterns of localisation, i.e. on the limiting occupational measure of VRRW. While the results generalize those of Pemantle and Volkov for \(G=Z^1\), the proofs are different and use large deviation principles instead of martingale arguments.
0 references
vertex-reinforced random walk
0 references
local time
0 references
large deviation principle
0 references
Polya urn model
0 references
martingales
0 references