A generalized Pólya's urn with graph based interactions: convergence at linearity
- Creators
- Chen, Jun
- Lucas, Cyrille
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
Name | Size | Download all |
---|---|---|
md5:dce72bb157de74b1ffd828a4fbb79cc0
|
210.1 kB | Preview Download |
md5:99e69711acb07a372d6fb16b4ee518d0
|
346.4 kB | Preview Download |
Additional details
- Eprint ID
- 53793
- Resolver ID
- CaltechAUTHORS:20150115-130415690
- Israel Science Foundation (ISF)
- Created
-
2015-01-15Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field