The exclusion process mixes (almost) faster than independent particles
The exclusion process mixes (almost) faster than independent particles
复制标题
排除过程混合（几乎）比独立粒子更快
DOI：
10.1214/20-aop1455
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Richard Pymar
中科院分区：
文献类型：
--
作者：
J. Hermon;Richard Pymar
Oliveira证明了任意n个顶点图上k个粒子的排斥过程的混合时间的阶数至多是k个独立粒子的混合时间的阶数.我们在各种情况下，当每条边以1/d$的速率环时，验证了$d$-正则图的这个常数因子：（1）当$d = \Omega（\log_{n/k} n）$时，（2）当$\mathrm{gap}：=$时，单次行走的谱间隙是$ O（1/\log^4 n）$和$k \ge n^{\Omega（1）}$，（3）当$k \asymp n^{a}$为某个常数$0<a<1$时。在这些情况下，我们的分析产生了一个概率证明的一个较弱版本的奥尔德斯著名的光谱间隙猜想（解决卡普托等人）。我们还证明了一个O（\log n \log \log n / \mathrm{gap}）的一般界，当k \ge n^{\Omega（1）}$时，它在Oliveira猜想的一个因子之内。作为应用，我们得到了新的混合边界：（a）对于扩张子，其混合边界为O（\log n \log \log n）$;（B）对于超立方体$\{0，1\}^d$，其混合边界为d\log（dk）$;（c）对于中等增长的点传递图和固定维环面上的超临界渗流，其混合边界为（\mathrm{Diameter}）^2 \log k $。
Oliveira conjectured that the order of the mixing time of the exclusion process with $k$-particles on an arbitrary $n$-vertex graph is at most that of the mixing-time of $k$ independent particles. We verify this up to a constant factor for $d$-regular graphs when each edge rings at rate $1/d$ in various cases: (1) when $d = \Omega( \log_{n/k} n)$, (2) when $\mathrm{gap}:=$ the spectral-gap of a single walk is $ O ( 1/\log^4 n) $ and $k \ge n^{\Omega(1)}$, (3) when $k \asymp n^{a}$ for some constant $0<a<1$. In these cases our analysis yields a probabilistic proof of a weaker version of Aldous' famous spectral-gap conjecture (resolved by Caputo et al.). We also prove a general bound of $O(\log n \log \log n / \mathrm{gap})$, which is within a $\log \log n$ factor from Oliveira's conjecture when $k \ge n^{\Omega (1)}$. As applications we get new mixing bounds: (a) $O(\log n \log \log n)$ for expanders, (b) order $ d\log (dk) $ for the hypercube $\{0,1\}^d$, (c) order $(\mathrm{Diameter})^2 \log k $ for vertex-transitive graphs of moderate growth and for supercritical percolation on a fixed dimensional torus.
快速的社交连接
影响因子：
1.4
作者：
Benjamini I
通讯作者：
Benjamini I
超图上排除过程的混合时间
影响因子：
1.4
作者：
Connor S
通讯作者：
Connor S