STRONGLY REINFORCED POLYA URNS WITH GRAPH-BASED COMPETITION

• 成果类型: Article
• 署名作者: van der Hofstad, Remco; Holmes, Mark; Kuznetsov, Alexey; Ruszel, Wioletta
• 署名单位: Eindhoven University of Technology; University of Auckland; York University - Canada; Delft University of Technology
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/16-AAP1153
• 发表日期: 2016
• 页码: 2494-2539
• 关键词: random-walk; edge

摘要

We introduce a class of reinforcement models where, at each time step t, one first chooses a random subset A(t) of colours (independently of the past) from n colours of balls, and then chooses a colour i from this subset with probability proportional to the number of balls of colour i in the urn raised to the power alpha > 1. We consider stability of equilibria for such models and establish the existence of phase transitions in a number of examples, including when the colours are the edges of a graph; a context which is a toy model for the formation and reinforcement of neural connections. We conjecture that for any graph G and all alpha sufficiently large, the set of stable equilibria is supported on so-called whisker-forests, which are forests whose components have diameter between 1 and 3.