Repository logo
 

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

Published version
Peer-reviewed

Change log

Authors

Dembo, Amir 
Ding, Jian 
Miller, JP 
Peres, Yuval 

Abstract

Given a finite, connected graph \SG, the lamplighter chain on \SG is the lazy random walk X on the associated lamplighter graph \SG⋄=\Z2≀\SG. The mixing time of the lamplighter chain on the torus \Znd is known to have a cutoff at a time asymptotic to the cover time of \Znd if d=2, and to half the cover time if d≥3. We show that the mixing time of the lamplighter chain on \ttorus=\Zn2×\Zalogn has a cutoff at ψ(a) times the cover time of \ttorus 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 \Zn2 and \Zn3. Perhaps surprisingly, we find a phase transition (non-smoothness of ψ) at the point a∗=πr3(1+2), where high dimensional behavior (ψ(a)=1/2 for all aa) commences. Here r3 is the effective resistance from 0 to in \Z3.

Description

Keywords

Wreath product, Lamplighter walk, Mixing time, Cutoff, Uncovered set

Journal Title

Probability Theory and Related Fields

Conference Name

Journal ISSN

1432-2064
1432-2064

Volume Title

173

Publisher

Springer Nature

Rights

All rights reserved