Cutoff for congestion dynamics and related generalized exclusion processes
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912226069184512 |
|---|---|
| author | Tanaka, Ryokichi |
| author_facet | Tanaka, Ryokichi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_06071 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cutoff for congestion dynamics and related generalized exclusion processes Tanaka, Ryokichi Probability Discrete Mathematics 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. |
| title | Cutoff for congestion dynamics and related generalized exclusion processes |
| topic | Probability Discrete Mathematics |
| url | https://arxiv.org/abs/2502.06071 |