论文标题
将重复球的时间混合到垃圾箱动力学
Mixing time for the Repeated Balls into Bins dynamics
论文作者
论文摘要
我们估计了一个不可逆的有限马尔可夫链的混合时间，称为重复的球键（RBB）过程。此过程是具有并行更新的离散时间保守交互粒子系统。最初以$ l $ bins $ rl $ balls的形式放置，其中$ r $是固定的正常数。在每个步骤中，从每个非空箱中取一个球。然后，\ emph {所有球}均匀地将其重新分成垃圾箱。我们证明，RBB过程的混合时间线性取决于初始状态的最大职业数量。因此，如果初始配置是使球的最大职业数量为订单$ l $，则混合时间为正确的顺序。虽然如果初始配置更稀释，则在订单$（\ log l）^c $的时间内达到平衡。
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 $(\log L)^c$.
