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

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. Previous works proved that when $G$ is not balanced bipartite, the proportion of balls in the bins converges to a point $w(G)$ almost surely. We prove almost sure convergence for balanced bipartite graphs: the possible limit is either a single point $w(G)$ or a closed interval $\mathcal{J}(G)$.

12 pages

References in corpus (1)

• A survey of random processes with reinforcement

Cited by in corpus (8)

• Synchronization of Reinforced Stochastic Processes with a Network-based Interaction
• Interacting reinforced stochastic processes: statistical inference based on the weighted empirical means
• Networks of reinforced stochastic processes: asymptotics for the empirical means
• WARM percolation on a regular tree in the strong reinforcement regime
• Networks of reinforced stochastic processes: a complete description of the first-order asymptotics
• Networks of reinforced stochastic processes: probability of asymptotic polarization and related general results
• Interacting non-linear reinforced stochastic processes: synchronization and no-synchronization
• Multiple colour interacting urns on complete graphs