A generalized Pólya's urn with graph based interactions. Issue 4 (21st November 2013) - Benaïm, Michel; Benjamini, Itai; Chen, Jun; Lima, Yuri
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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7rtmq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />α>0</alternatives>. 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7rtjp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />α<1</alternatives> then there is a single point <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7rtf4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />v=v(G, α)</alternatives> with non‐zero entries such that the proportion converges to v almost surely. A special case is when G is regular and <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7rt92" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />α≤1</alternatives>. 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