Strongly reinforced Pólya urns with graph-based competition

Journal article (2016)

Authors

Remco Van Der Hofstad Eindhoven University of Technology

Mark Holmes The University of Auckland

Alexey Kuznetsov York University

W.M. Ruszel Applied Probability -

Research Group

Applied Probability () (TU Delft)

Reinforcement model Pólya urn Stochastic approximation algorithm Stable equilibria

To reference this document use:

http://resolver.tudelft.nl/uuid:a656fb6e-97b8-4731-8e2b-8319981203d8

More Info

expand_more

Published Date

2016

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Applied Probability

Abstract

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.