A generalized Pólya's urn with graph based interactions |
| |
| Authors: | Michel Benaïm Itai Benjamini Jun Chen Yuri Lima |
| |
| Affiliation: | 1. Institut de Mathématiques, Université de Neuchatel, Neuchatel, Suisse;2. Weizmann Institute of Science, Faculty of Mathematics and Computer Science, Rehovot, Israel;3. Department of Mathematics, University of Maryland, College Park, Maryland |
| |
| 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 |
| |
| Keywords: | gradient‐like system Pó lya's urn reinforcement stochastic approximation algorithms unstable equilibria |
|
|
