A direct comparison between the mixing time of the interchange process with "few" particles and independent random walks

Jonathan Hermon, Richard Pymar

Published 2021-05-27Version 1

We consider the interchange process with $k$ particles (${\rm IP}(k)$) on $n$-vertex hypergraphs in which each hyperedge $e$ rings at rate $r_e$. When $e$ rings, the particles occupying it are permuted according to a random permutation from some arbitrary law, where our only assumption is that ${\rm IP}(2)$ has uniform stationary distribution. We show that $t_{\rm mix}^{{\rm IP}(k)}(\epsilon)=O_{b}(t_{\rm mix}^{{\rm IP}(2)}(\epsilon/k))$, where $t_{\rm mix}^{{\rm IP}(i)}(\epsilon)$ is the $\epsilon$ total-variation mixing time of ${\rm IP}(i)$, provided that $kn^{-2}Rt_{\rm mix}^{{\rm IP}(2)}(\epsilon/k)=O((\epsilon/k)^b)$ for some $b>0$, where $R=\sum_e r_e|e|(|e|-1)$ is $n(n-1)$ times the particle-particle interaction rate at equilibrium. This has some consequences concerning the validity in this regime of conjectures of Oliveira about comparison of the $\epsilon$ mixing time of ${\rm IP}(k)$ to that of $k$ independent particles, each evolving according to ${\rm IP}(1)$, denoted ${\rm RW}(k)$, and of Caputo about comparison of the spectral-gap of ${\rm IP}(k)$ to that of a single particle ${\rm IP}(1)={\rm RW}(1)$. We also show that $t_{\rm mix}^{\mathrm{IP}(k)}(\epsilon) \asymp t_{\rm mix}^{{\rm RW}(1)}(\epsilon)\asymp t_{{\rm mix}}^{{\rm RW}(k)}(\epsilon k/4)$ for all $k\lesssim n^{1-\Omega(1)}$ and all $\epsilon\le\frac 1k\wedge\frac 14$ for vertex-transitive graphs of constant degree, as well as for general graphs satisfying a mild ("transience-like") heat-kernel condition. In the case where the particles occupying a hyperedge $e$ are permuted uniformly at random when $e$ rings we obtain results bounding the spectral gap of ${\rm IP}(k)$ in terms of that ${\rm RW}(1)$. The proof does not use Morris' chameleon process. It can be seen as a rigorous and direct way of arguing that when the number of particles is fairly small, the system behaves similarly to $k$ independent particles.