×

A generalized Pólya’s urn with graph based interactions. (English) Zbl 1317.05103

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 raised by some fixed power \(\alpha >0\). We characterize the limiting behavior of the proportion of balls in the bins.{ }The proof uses a dynamical approach to relate the proportion of balls to a vector field. Our main result is that the limit set of the proportion of balls is contained in the equilibria set of the vector field. We also prove that if \(\alpha<1\) then there is a single point \(v=v(G,\alpha)\) with non-zero entries such that the proportion converges to \(v\) almost surely.{ }A special case is when \(G\) is regular and \(\alpha\geq 1\). We show e.g. that if \(G\) is non-bipartite then the proportion of balls in the bins converges to the uniform measure almost surely.

MSC:

05C40 Connectivity
05C81 Random walks on graphs
68W25 Approximation algorithms

References:

[1] N.Alon and J.H.Spencer, The probabilistic method, 3rd edition, Wiley‐Interscience Series in Discrete Mathematics and Optimization, 2008. · Zbl 1148.05001
[2] M.Benaï m, A dynamical system approach to stochastic approximations, SIAM J Control Optim34 (1996), 437-472. · Zbl 0841.62072
[3] M.Benaïm, Dynamics of stochastic approximation algorithms, Séminaire de Probabilités XXXIII, 1999, pp. 1-68. · Zbl 0955.62085
[4] M.Benaï m, O.Raimond, and B.Schapira, Strongly reinforced vertex‐reinforced‐random‐walk on the complete graph, preprint arXiv:1208.6375 (2012).
[5] J.Chen and C.Lucas, Generalized P olya’s u rn: Convergence at linearity, preprint arXiv:1306.5465 (2013).
[6] F.Chung, S.Handjani, and D.Jungreis, Generalizations of P olya’s urn problem, Ann Comb7 (2003), 141-153. · Zbl 1022.60005
[7] R.Durrett, Probability: theory and examples, series= Cambridge Series in Statistical and Probabilistic Mathematics Cambridge University Press, Cambridge, 2010. · Zbl 1202.60001
[8] B. M.Hill, D.Lane, and W.Sudderth, A strong law for some generalized urn processes, Ann Probab8 (1980), 214-226. · Zbl 0429.60021
[9] M. O.Jackson, Social and economic networks, Princeton University Press, Princeton, NJ, 2008. · Zbl 1149.91051
[10] J.Kiefer and J.Wolfowitz, Stochastic estimation of the maximum of a regression function, Ann Math Stat23 (1952) 462-466. · Zbl 0049.36601
[11] H. J.Kushner and D. S.Clark, Stochastic approximation methods for constrained and unconstrained systems, Appl Math Sci, Vol. 26, Springer‐Verlag, New York‐Berlin, 1978. · Zbl 0381.60004
[12] M.Launay, Interacting urn models, arXiv:1101.1410 (2011).
[13] L.Ljung, Analysis of recursive stochastic algorithms, IEEE Trans Automatic Control AC‐22 (1977), 551-575. · Zbl 0362.93031
[14] M.Marsili and A.Valleriani, Self organization of interacting Polya urns, Eur Phys J B3 (1998), 417-420.
[15] H.Ohtsuki, C.Hauert, E.Lieberman, and M. A.Nowak, A simple rule for the evolution of cooperation on graphs and social networks, Nature441 (2006), 502-505.
[16] R.Pemantle, Vertex‐reinforced random walk, Probab Theory Related Fields92 (1992), 117-136. · Zbl 0741.60029
[17] R.Pemantle, A survey of random processes with reinforcement, Probab Surv4 (2007), 1-79. · Zbl 1189.60138
[18] H.Robbins and S.Monro, A stochastic approximation method, Ann Math Stat22 (1951), 400-407. · Zbl 0054.05901
[19] F. C.Santos, J. M.Pacheco, and T.Lenaerts, Evolutionary dynamics of social dilemmas in structured heterogeneous populations, Proc Nat Acad Sci USA103 (2006), 3490-3494.
[20] B.Skyrms and R.Pemantle, A dynamic model of social network formation, Proc Nat Acad Sci USA97 (2000), 9340-9346. · Zbl 0984.91013
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.