# 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.

##### MSC:
 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: