Vertex-reinforced random walks and a conjecture of pemantle

• 成果类型: Article
• 署名作者: Benaïm, M
• 署名单位: Universite de Toulouse; Universite Toulouse III - Paul Sabatier
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• 发表日期: 1997
• 页码: 361-392
• 关键词: stochastic approximations; algorithms; DYNAMICS

摘要

We discuss and disprove a conjecture of Pemantle concerning vertex-reinforced random walks. The setting is a general theory of non-Markovian discrete-time random processes on a finite space E = {1,...,d}, for which the transition probabilities at each step are influenced by the proportion of times each state has been visited. It is shown that, under mild conditions, the asymptotic behavior of the empirical occupation measure of the process is precisely related to the asymptotic behavior of some deterministic dynamical system induced by a vector field on the d - 1 unit simplex. In particular, any minimal attractor of this vector field has a positive probability to be the Limit set of the sequence of empirical occupation measures. These properties are used to disprove a conjecture and to extend some results due to Pemantle. Some applications to edge-reinforced random walks are also considered.