Strongly reinforced pólya urns with graph-based competition

R.W. van der Hofstad, M. Holmes, A. Kuznetsov, W.M. Ruszel

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)
104 Downloads (Pure)


We introduce a class of reinforcement models where, at each time step t, one first chooses a random subset At 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 α >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 α 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.

Original languageEnglish
Pages (from-to)2494-2539
Number of pages46
JournalThe Annals of Applied Probability
Issue number4
Publication statusPublished - 1 Aug 2016


  • Pólya urn
  • Reinforcement model
  • Stable equilibria.
  • Stochastic approximation algorithm


Dive into the research topics of 'Strongly reinforced pólya urns with graph-based competition'. Together they form a unique fingerprint.

Cite this