Lima, Yuri Graph-based Pólya’s urn: completion of the linear case. (English) Zbl 1335.60185 Stoch. Dyn. 16, No. 2, Article ID 1660007, 13 p. (2016). Summary: 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 M. Benaïm et al. [Random Struct. Algorithms 46, No. 4, 614–634 (2015; Zbl 1317.05103)]. When \(G\) is not balanced bipartite, J. Chen and C. Lucas [Electron. Commun. Probab. 19, Paper No. 67, 13 p. (2014; Zbl 1326.60135)] proved that 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)\). Cited in 6 Documents MSC: 60K35 Interacting random processes; statistical mechanics type models; percolation theory 60F15 Strong limit theorems 60C05 Combinatorial probability 37C10 Dynamics induced by flows and semiflows Keywords:Pólya’s urn; balanced bipartite graphs; almost sure convergence; gradient-like system; reinforcement; stochastic approximation algorithm Citations:Zbl 1317.05103; Zbl 1326.60135 PDFBibTeX XMLCite \textit{Y. Lima}, Stoch. Dyn. 16, No. 2, Article ID 1660007, 13 p. (2016; Zbl 1335.60185) Full Text: DOI arXiv References: [1] 1. M. Benaïm, I. Benjamini, J. Chen and Y. Lima, A generalized Pólya’s urn with graph based interactions, Random Structures Algorithms46 (2015) 614-634. genRefLink(16, ’S0219493716600078BIB001’, ’10.1002 [2] 2. M. Benaïm, A dynamical system approach to stochastic approximations, SIAM J. Control Optim.34 (1996) 437-472. genRefLink(16, ’S0219493716600078BIB002’, ’10.1137 [3] 3. M. Benaïm, Dynamics of stochastic approximation algorithms, Séminaire de Probabilités. Lecture Notes in Math.1709 (1999) 1-68. genRefLink(16, ’S0219493716600078BIB003’, ’10.1007 [4] 4. J. Chen and C. Lucas, A generalized Pólya’s urn with graph based interactions: Convergence at linearity, Electron. Commun. Probab.19 (2014) 67. genRefLink(16, ’S0219493716600078BIB004’, ’10.1016 [5] 5. M. W. Hirsch, C. C. Pugh and M. Shub, Invariant Manifolds, Lecture Notes in Mathematics, Vol. 583 (Springer-Verlag, 1977). [6] 6. R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd edn. (Cambridge Univ. Press, 2013). · Zbl 1267.15001 [7] 7. R. Pemantle. Vertex-reinforced random walk, Probab. Theory Rel. Fields92 (1992) 117-136. genRefLink(16, ’S0219493716600078BIB007’, ’10.1007 [8] 8. R. Pemantle, A survey of random processes with reinforcement, Probab. Surv.4 (2007) 1-79. genRefLink(16, ’S0219493716600078BIB008’, ’10.1214 · Zbl 1189.60138 [9] 9. B. Skyrms and R. Pemantle, A dynamic model of social network formation, Proc. Natl. Acad. Sci. USA97 (2000) 9340-9346. genRefLink(16, ’S0219493716600078BIB009’, ’10.1073 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.