×

Graph-based Pólya’s urn: completion of the linear case. (English) Zbl 1335.60185

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)\).

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
PDFBibTeX XMLCite
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.