Graph-based Polya's urn: Completion of the linear case

摘要

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. This model was introduced by Benaim, Benjamini, Chen, and Lima. When G is not balanced bipartite, Chen and Lucas proved that the proportion of balls in the bins converges to a point w(G) almost surely.