Cut-off for lamplighter chains on tori: dimension interpolation and Phase transition

• 成果类型: Article
• 署名作者: Dembo, Amir; Ding, Jian; Miller, Jason; Peres, Yuval
• 署名单位: Stanford University; University of Pennsylvania; University of Cambridge; Microsoft
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-018-0883-4
• 发表日期: 2019
• 页码: 605-650
• 关键词: random-walks; cover times

摘要

Given a finite, connected graph G, the lamplighter chain on G is the lazy random walk X on the associated lamplighter graph G=Z2G. The mixing time of the lamplighter chain on the torus Zndis known to have a cutoff at a time asymptotic to the cover time of Zndif d=2, and to half the cover time if d3. We show that the mixing time of the lamplighter chain on Gn(a)=Zn2xZalogn has a cutoff at (a) times the cover time of Gn(a) as n, where is an explicit weakly decreasing map from (0,) onto [1/2,1). In particular, as a>0 varies, the threshold continuously interpolates between the known thresholds for Zn2and Zn3. Perhaps surprisingly, we find a phase transition (non-smoothness of ) at the point r3(1+), where high dimensional behavior ((a)=1/2 for all aa) commences. Here r3 is the effective resistance from 0 to in Z3.