Vertex-reinforced random walk on arbitrary graphs
Vertex-reinforced random walk on arbitrary graphs
复制标题
任意图上的顶点强化随机游走
DOI：
10.1214/aop/1008956322
复制
发表时间：
1999
影响因子：
2.3
通讯作者：
S. Volkov
中科院分区：
文献类型：
--
作者：
S. Volkov
Pemantle 定义的顶点强化随机游走 (VRRW) 是一个在不断变化的环境中的随机过程，该过程更有可能访问之前访问过的状态。我们在任意图上考虑 VRRW，并表明在几乎所有图上，VRRW 仅以正概率访问有限多个顶点。我们推测，在所有有界度图上，这种情况发生的概率为 1，并且只为这种类型的树提供证明。我们区分了几种不同的定位模式，并明确描述了 VRRW 的长期结构，这取决于图是否包含三角形。虽然本文的结果概括了 Pemantle 和 Volkov 对于 Z 1 获得的结果，但证明的想法不同，并且通常基于大偏差原理而不是鞅方法。
Vertex-reinforced random walk (VRRW), defined by Pemantle, 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 with probability 1, 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 for Z 1 , ideas of proofs are different and typically based on a large deviation principle rather than a martingale approach.