Mixing time for the repeated balls into bins dynamics

DOI10.1214/20-ECP338MaRDI QIDQ2201539zbMATH OpenOpenAlexFDO

Authors N. Cancrini, Gustavo Posta

Publication date 29 September 2020

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.11246, https://projecteuclid.org/euclid.ecp/1597111630

zbMATH Keywords

couplingmixing timesinteracting particles systemsparallel updatesqueues networks

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We estimate the mixing time of the 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 taken from each non-empty bin. Then emph{all the balls} are uniformly reassigned into bins. We prove that the mixing time of the RBB process depends linearly on the maximum occupation number of balls of the initial state. Thus if the initial configuration is such that the maximum occupation number of balls is of order $L$ then the mixing time is of the same correct order. While if the initial configuration is more diluted then the equilibrium is reached in a time of order $(logL{)}^c$.

Recommendations

• Mixing times for the simple exclusion process in ballistic random environment
• Recurrence times and rates of mixing
• The distribution of mixing times in Markov chains
• Mixing times are hitting times of large sets
• Mixing times of random walks on dynamic configuration models
• The mixing time for simple exclusion
• From rates of mixing to recurrence times via large deviations
• Mixing time of Markov chains, dynamical systems and evolution
• Mixing and average mixing times for general Markov processes

Cites work

• scientific article; zbMATH DE number 3892344 (Why is no real title available?)
• Balls and bins: A study in negative dependence
• Cutoff for the mean-field zero-range process with bounded monotone rates
• Ergodicity of PCA: equivalence between spatial and temporal mixing conditions
• Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling
• Interaction of Markov processes
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Networks of queues
• Propagation of chaos for a balls into bins model
• Self-stabilizing repeated balls-into-bins

Cited in

(4)

• Propagation of chaos for a balls into bins model
• Self-stabilizing repeated balls-into-bins
• Entry times distribution for mixing systems
• Propagation of chaos for a general balls into bins dynamics

This page was built for publication: Mixing time for the repeated balls into bins dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2201539)