zbMATH — the first resource for mathematics

Propagation of chaos for a balls into bins model. (English) Zbl 1406.60128
Summary: Consider a finite number of balls initially placed in \(L\) bins. At each time step a ball is taken from each non-empty bin. Then all the balls are uniformly reassigned into bins. This finite Markov chain is called Repeated Balls-into-Bins process and is a discrete time interacting particle system with parallel updating. We prove that, starting from a suitable (chaotic) set of initial states, as \(L\rightarrow +\infty \), the numbers of balls in each bin become independent from the rest of the system i.e. we have propagation of chaos. We furthermore study some equilibrium properties of the limiting nonlinear process.

60K35 Interacting random processes; statistical mechanics type models; percolation theory
60B10 Convergence of probability measures
Full Text: DOI Euclid arXiv
[1] L. Andreis, P. Dai Pra, M. Fischer: McKean-Vlasov limit for interacting systems with simultaneous jumps, arXiv:1704.01052. · Zbl 1401.92022
[2] L. Becchetti, A. Clementi, E. Natale, F. Pasquale, G. Posta: Self-stabilizing repeated balls-into-bins. Distrib. Comput. (2017), 1–10. · Zbl 1451.60080
[3] P. Billingsley: Probability and measure (third edition). John Wiley & Sons, New York, 1995. · Zbl 0822.60002
[4] B. Fristedt, L. Gray: A modern approach to probability theory. Birkhäuser, Boston, 1997. · Zbl 0869.60001
[5] J. R. Jackson: Jobshop-like queueing systems. Management Sciences Research Project81 (1963).
[6] M. Kac: Foundations of kinetic theory. Proceedings of the Third Berkley Symposium on Mathematical Statistics and Probability 1954–1955III, University of California Press, Berkley and Los Angeles, 1956, 171–197.
[7] F. P. Kelly: Networks of queues. Advances in Appl. Probability8 (1976), no. 2, 416–432.
[8] A. K. Erlang: Sandsynlighedsregning Og Telefonsamtaler. Nyt Tidsskrift for Matematik20 (1909), 33–39. · JFM 40.0281.01
[9] K. Nakagawa: On the series expansion of the stationary probabilities of an M/D/1 queue, J. Oper. Res. Soc. Japan48 (2005) no. 2, 111–122. · Zbl 1078.60079
[10] F. Spitzer: Interaction of Markov processes. Advances in Math.5 (1970), 246–290. · Zbl 0312.60060
[11] A-S. Sznitman: Topics in propagation of chaos. École d’Été de Probabilités de Saint-Flour XIX-1989, Lecture Notes in Mathematics1464, Springer, Berlin, 1991, 165–251.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.