A generalized Polya's urn with graph based interactions

Abstract

Given a finite connected graph G, place a bin at each vertex. Two bins are called a pair if they share an edge of G. At discrete times, a ball is added to each pair of bins. In a pair of bins, one of the bins gets the ball with probability proportional to its current number of balls raised by some fixed power a>0. We characterize the limiting behavior of the proportion of balls in the bins. The proof uses a dynamical approach to relate the proportion of balls to a vector field. Our main result is that the limit set of the proportion of balls is contained in the equilibria set of the vector field. We also prove that if a<1 then there is a single point v=v(G,a) with nonzero entries such that the proportion converges to v almost surely. A special case is when G is regular and a is at most 1. We show e.g. that if G is non-bipartite then the proportion of balls in the bins converges to the uniform measure almost surely.

arXiv comment20 pages, to appear in Random Structures and Algorithms

References in corpus (5)

• A survey of random processes with reinforcement
• Self Organization of Interacting Polya Urns
• Strongly Vertex-Reinforced-Random-Walk on the complete graph
• Interacting Urn Models
• A generalized Pólya's Urn with graph based interactions: convergence at linearity

Cited by in corpus (18)

• Interacting generalized Friedman's urn systems
• Coexistence in preferential attachment networks
• Synchronization of Reinforced Stochastic Processes with a Network-based Interaction
• Graph-based Polya's urn: completion of the linear case
• Interacting reinforced stochastic processes: statistical inference based on the weighted empirical means
• Networks of reinforced stochastic processes: asymptotics for the empirical means
• Localisation in a growth model with interaction
• WARM percolation on a regular tree in the strong reinforcement regime
• Weakly reinforced Pólya urns on countable networks
• Vertex reinforced random walks with exponential interaction on complete graphs
• Networks of reinforced stochastic processes: a complete description of the first-order asymptotics
• Quenched law of large numbers and quenched central limit theorem for multi-player leagues with ergodic strengths
• Asymptotics of generalized Pólya urns with non-linear feedback
• Wages and Capital returns in a generalized Pólya urn
• Interacting non-linear reinforced stochastic processes: synchronization and no-synchronization
• Urns with Multiple Drawings and Graph-Based Interaction
• Networks of reinforced stochastic processes: probability of asymptotic polarization and related general results
• Multiple colour interacting urns on complete graphs