Mixing time for the repeated balls into bins dynamics

DOI10.1214/20-ECP338zbMATH Open1469.60313arXiv2001.11246OpenAlexW3048425935MaRDI QIDQ2201539FDOQ2201539

Gustavo Posta, N. Cancrini

Publication date: 29 September 2020

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

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$.

Full work available at URL: https://arxiv.org/abs/2001.11246

zbMATH Keywords

couplingmixing timesinteracting particles systemsparallel updatesqueues networks

Mathematics Subject Classification ID

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

Cites Work

• Interaction of Markov processes
• Title not available (Why is that?)
• Balls and bins: A study in negative dependence
• Ergodicity of PCA: equivalence between spatial and temporal mixing conditions
• Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling
• Networks of queues
• Title not available (Why is that?)
• Cutoff for the mean-field zero-range process with bounded monotone rates
• Propagation of chaos for a balls into bins model
• Self-stabilizing repeated balls-into-bins

Cited In (2)

• Entry times distribution for mixing systems
• Propagation of chaos for a general balls into bins dynamics

   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 👍 👎

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)