A generalized Pólya's urn with graph based interactions

Abstract

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 . 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 then there is a single point with non‐zero entries such that the proportion converges to v almost surely. A special case is when G is regular and . 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.Copyright © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,614–634, 2015

Locations

• arXiv (Cornell University) - View - PDF
• CiteSeer X (The Pennsylvania State University) - View - PDF
• DataCite API - View
• Random Structures and Algorithms - View