Vertex-reinforced random walk on arbitrary graphs

Details Vertex-reinforced random walk on arbitrary graphs Vertex-reinforced random walk on arbitrary graphs

1999-07-23

arxiv.org/abs/math/9907196v1

Mathematics

Probability

Scientific paper

Vertex-Reinforced Random Walk (VRRW), defined by Pemantle (1988a), is a random process in a continuously changing environment which is more likely to visit states it has visited before. We consider VRRW on arbitrary graphs and show that on almost all of them, VRRW visits only finitely many vertices with a positive probability. We conjecture that on all graphs of bounded degree, this happens a.s., and provide a proof only for trees of this type. We distinguish between several different patterns of localization and explicitly describe the long-run structure of VRRW, which depends on whether a graph contains triangles or not. While the results of this paper generalize those obtained by Pemantle and Volkov (1998) for Z,ideas of proofs are different and typically based on a large deviation principle rather than a martingale approach.

Affiliated with

Also associated with

No associations

Rating

Vertex-reinforced random walk on arbitrary graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Vertex-reinforced random walk on arbitrary graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vertex-reinforced random walk on arbitrary graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-198577