Cutoff for congestion dynamics and related generalized exclusion processes

Abstract

We consider congestion dynamics with $n$ players and $Q$ resources under the constraint that the number of each resource is $\hat{I}º$ and that $n<\hat{I}ºQ$ in the regime that $n$ and $\hat{I}º$ diverge but $Q$ is fixed with $n=\lfloor \ddot{I}\hat{I}ºQ\rfloor$ for a fixed constant $\ddot{I}\in (0,1/2]$. We show that the Glauber dynamics and its unlabeled version exhibit cutoff at time $(1/2)n\log n$ and $(1/2)(1-\ddot{I})n\log n$ in total variation respectively. The unlabeled version is a special case of natural Markov chains for sampling from log M-concave distributions. We also show that a family of Markov chains for uniform sampling on M-convex sets does not necessarily exhibit cutoff.

31 pages, 2 figures