

























We consider congestion dynamics with $n$ players and $Q$ resources under the constraint that the number of each resource is $κ$ and that $n<κQ$ in the regime that $n$ and $κ$ diverge but $Q$ is fixed with $n=\lfloor{ρκQ\rfloor}$ for a fixed constant $ρ\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-ρ)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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。