Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 3, 2014 | Submitted + Published
Journal Article Open

A generalized Pólya's urn with graph based interactions: convergence at linearity

Abstract

We consider a special case of the generalized Polya's urn model introduced in 3]. 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.

Additional Information

© 2014 Institute of Mathematical Statistics. This work is licensed under a Creative Commons Attribution 3.0 License. Submitted to ECP on October 25, 2013, final version accepted on September 24, 2014. The authors are thankful to Michel Benaïm, Itai Benjamini and Pascal Maillard for many enlightening discussions, as well as Ofer Zeitouni for substantial help in the proof of Theorem 1.2. During the preparation of this manuscript, J.C. was a student and C.L. was a Postdoctoral Fellow at the Weizmann Institute of Science. Both authors were supported by the ISF. Finally, the authors would like to thank Yuri Lima for suggesting the simpler proof of Theorem 1.2 presented here.

Attached Files

Published - 3094-18886-3-PB.pdf

Submitted - 1306.5465v2.pdf

Files

1306.5465v2.pdf
Files (556.4 kB)
Name Size Download all
md5:dce72bb157de74b1ffd828a4fbb79cc0
210.1 kB Preview Download
md5:99e69711acb07a372d6fb16b4ee518d0
346.4 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 19, 2023