zbMATH — the first resource for mathematics

A generalized Pólya’s urn with graph based interactions: convergence at linearity. (English) Zbl 1326.60135
Summary: We consider a special case of the generalized Pólya’s urn model. 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. A question of essential interest for the model is to understand the limiting behavior of the proportion of balls in the bins for different graphs \(G\). In this paper, we present two results regarding this question. If \(G\) is not balanced-bipartite, we prove that the proportion of balls converges to some deterministic point \(v=v(G)\) almost surely. If \(G\) is regular bipartite, we prove that the proportion of balls converges to a point in some explicit interval almost surely. The question of convergence remains open in the case when \(G\) is non-regular balanced-bipartite.

60K35 Interacting random processes; statistical mechanics type models; percolation theory
60F15 Strong limit theorems
05C99 Graph theory
37C10 Dynamics induced by flows and semiflows
Full Text: DOI arXiv