We consider a nonreversible finite Markov chain called Repeated Balls-into-Bins (RBB) process. This process is a discrete time conservative interacting particle system with parallel updates. Place initially in L bins rL balls, where r is a fixed positive constant. At each time step a ball is removed from each non-empty bin. Then all these removed balls are uniformly reassigned into bins. We prove that the mixing time of the RBB process is of order L. Furthermore we show that if the initial configuration has o(L) balls per site the equilibrium is attained in o(L) steps.

Mixing time for the repeated balls into bins dynamics / Cancrini, N.; Posta, G.. - In: ELECTRONIC COMMUNICATIONS IN PROBABILITY. - ISSN 1083-589X. - 25:0(2020), pp. 1-14. [10.1214/20-ECP338]

Mixing time for the repeated balls into bins dynamics

Cancrini N.;Posta G.
2020

Abstract

We consider a nonreversible finite Markov chain called Repeated Balls-into-Bins (RBB) process. This process is a discrete time conservative interacting particle system with parallel updates. Place initially in L bins rL balls, where r is a fixed positive constant. At each time step a ball is removed from each non-empty bin. Then all these removed balls are uniformly reassigned into bins. We prove that the mixing time of the RBB process is of order L. Furthermore we show that if the initial configuration has o(L) balls per site the equilibrium is attained in o(L) steps.
2020
Coupling; interacting particles systems; mixing times; parallel updates; queues networks
01 Pubblicazione su rivista::01a Articolo in rivista
Mixing time for the repeated balls into bins dynamics / Cancrini, N.; Posta, G.. - In: ELECTRONIC COMMUNICATIONS IN PROBABILITY. - ISSN 1083-589X. - 25:0(2020), pp. 1-14. [10.1214/20-ECP338]
File allegati a questo prodotto
File Dimensione Formato  
Cancrini_Mixing-time_2020.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 249.42 kB
Formato Adobe PDF
249.42 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1452019
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact