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

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 <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/rsa20523-math-0001.png" xlink:title="urn:x-wiley::media:rsa20523:rsa20523-math-0001" />. 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 <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/rsa20523-math-0002.png" xlink:title="urn:x-wiley::media:rsa20523:rsa20523-math-0002" /> then there is a single point <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/rsa20523-math-0003.png" xlink:title="urn:x-wiley::media:rsa20523:rsa20523-math-0003" /> with non‐zero entries such that the proportion converges to <jats:italic>v</jats:italic> almost surely.</jats:p><jats:p>A special case is when <jats:italic>G</jats:italic> is regular and <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/rsa20523-math-0004.png" xlink:title="urn:x-wiley::media:rsa20523:rsa20523-math-0004" />. 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.