MIXING OF THE SYMMETRIC EXCLUSION PROCESSES IN TERMS OF THE CORRESPONDING SINGLE-PARTICLE RANDOM WALK

被引:20
作者
Oliveira, Roberto Imbuzeiro [1 ]
机构
[1] IMPA, BR-22460320 Rio De Janeiro, RJ, Brazil
关键词
Symmetric exclusion; interchange process; mixing time; LOGARITHMIC SOBOLEV INEQUALITY; SPECTRAL GAP; TIME; PERCOLATION; CLUSTER; BOUNDS;
D O I
10.1214/11-AOP714
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
We prove an upper bound for the epsilon-mixing time of the symmetric exclusion process on any graph G, with any feasible number of particles. Our estimate is proportional to T-RW(G) ln(vertical bar V vertical bar/epsilon), where vertical bar V vertical bar is the number of vertices in G, and T-RW(G) is the 1/4-mixing time of the corresponding single-particle random walk. This bound implies new results for symmetric exclusion on expanders, percolation clusters, the giant component of the Erdos-Renyi random graph and Poisson point processes in R-d. Our technical tools include a variant of Morris's chameleon process.
引用
收藏
页码:871 / 913
页数:43
相关论文
共 23 条
[1]  
Alon N., 2000, PROBABILISTIC METHOD
[2]   A CORRELATION-INEQUALITY FOR THE SYMMETRIC EXCLUSION PROCESS [J].
ANDJEL, ED .
ANNALS OF PROBABILITY, 1988, 16 (02) :717-721
[3]  
[Anonymous], REVERSIBLE MAR UNPUB
[4]   On the mixing time of a simple random walk on the super critical percolation cluster [J].
Benjamini, I ;
Mossel, E .
PROBABILITY THEORY AND RELATED FIELDS, 2003, 125 (03) :408-420
[5]   Isoperimetric inequalities and mixing time for a random walk on a random point process [J].
Caputo, Pietro ;
Faggionato, Alessandra .
ANNALS OF APPLIED PROBABILITY, 2007, 17 (5-6) :1707-1744
[6]   PROOF OF ALDOUS' SPECTRAL GAP CONJECTURE [J].
Caputo, Pietro ;
Liggett, Thomas M. ;
Richthammer, Thomas .
JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 2010, 23 (03) :831-851
[7]  
Cooper C, 2009, LECT NOTES COMPUT SC, V5556, P399, DOI 10.1007/978-3-642-02930-1_33
[8]  
Diaconis P, 1996, ANN APPL PROBAB, V6, P695
[9]  
DIACONIS P., 1993, The Annals of Applied Probability, V3, P696, DOI DOI 10.1214/AOAP/1177005359
[10]   INTERLACINGS FOR RANDOM WALKS ON WEIGHTED GRAPHS AND THE INTERCHANGE PROCESS [J].
Dieker, A. B. .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (01) :191-206